Bitwise operation problem

This is a discussion on Bitwise operation problem within the C++ Programming forums, part of the General Programming Boards category; Another bitwise problem I'm working on now is this: Code: /* * bitMask - Generate a mask consisting of all ...

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    271

    Bitwise operation problem

    Another bitwise problem I'm working on now is this:

    Code:
    /* 
     * bitMask - Generate a mask consisting of all 1's 
     *   lowbit and highbit
     *   Examples: bitMask(5,3) = 0x38
     *   Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
     *   If lowbit > highbit, then mask should be all 0's
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 16
     *   Rating: 3
     */
    int bitMask(int highbit, int lowbit) {
        return 2;
    }
    Anyway, here's my solution to this problem:
    Code:
    /* 
     * bitMask - Generate a mask consisting of all 1's 
     *   lowbit and highbit
     *   Examples: bitMask(5,3) = 0x38
     *   Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
     *   If lowbit > highbit, then mask should be all 0's
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 16
     *   Rating: 3
     */
    int bitMask(int highbit, int lowbit) {
    	int i = 0, j = 0;
    	i = ~i;
    	i <<= highbit + 1;
    	j = ~j;
    	j <<= lowbit;
    	i ^= j;
    	return i & j;
    }
    My code works fine except for one case: when the highbit is 31.

    Somehow the bitwise operator works when it's:
    Code:
    i <<= 31; // i is 11111111111111111111111111111111 (32 digits)
    But it won't shift the leftmost significant bit when I do this:
    Code:
    i <<= 32; // nothing happens. in the next line, i is still -1
    Can anyone tell me why my compiler won't shift the entire thing to the left? (I'm using VC++ 2003, btw)

    And how do I go about it?

  2. #2
    Registered User
    Join Date
    Aug 2005
    Posts
    10
    My solution:

    Code:
    int bitMask(int highbit, int lowbit)
    	{
    	unsigned int i = 0;
    	i = ~i;
    	i <<= 32 - ((highbit-lowbit) + 1);
    	i >>= 32 - (highbit + 1);
    	return i;
    	}
    
    int main()
    	{
    	std::cout << bitMask(5,3) << "\n";
    	getchar();
    	return 0;
    	}
    Doesn't seem to work when lowbit > highbit though.

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Ugly and cryptic for amusement only:
    Code:
    int bitMask(int highbit, int lowbit) {
        return ((((~0U<<highbit)^(~0U<<lowbit))|(1<<highbit))>>lowbit)<<lowbit;
    }
    [edit]Oops.
    Quote Originally Posted by cunnus88
    Can anyone tell me why my compiler won't shift the entire thing to the left? (I'm using VC++ 2003, btw)
    With regard to this, the C standard says it like this:
    If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
    Last edited by Dave_Sinkula; 11-30-2005 at 11:43 PM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #4
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by cunnus88
    Can anyone tell me why my compiler won't shift the entire thing to the left? (I'm using VC++ 2003, btw)
    This is not the compiler. The compiler does not shift anything. It generates machine code.

    The compiler even generates the machine code correctly. My copy of gcc generates the assembly lines
    Code:
            movb    $32, %cl
            sall    %cl, %eax
    which when assembled will seemingly tell the processor to shift the register eax to the left by 32 bits.

    The processor itself gives the behavior. It looks only at the five least significant bits of the argument. On most thirty-two bit Intel processors with the IA-32 instruction set, the code x << s is always equivalent to x << (s & 31). The exception is the ancient 8086. (This information comes from the IA-32 Intel Architecture Software Developerís Manual.)

    You asked why, and the reason is almost certainly that by only looking at the least significant five bits, this makes the circuit simpler and faster.

  5. #5
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    With regard to this, the C standard says it like this:The results are undefined if the right operand of a shift expression is negative or if the right operand is greater than or equal to the number of bits in the (promoted) left operand.
    MSDN as well:
    The results are undefined if .... the right operand is greater than or equal to the number of bits in the (promoted) left operand.
    http://msdn.microsoft.com/library/de..._operators.asp

  6. #6
    Registered User
    Join Date
    Oct 2005
    Posts
    271
    Thanks everyone, for taking the time to reply. So I take it that there is no way to shift that final most significant bit so that it becomes a 0?

    I tried Dave's code as a lark, and it worked! (even when the highbit was 31)

    Quote Originally Posted by Dave_Sinkula
    Ugly and cryptic for amusement only:
    Code:
    int bitMask(int highbit, int lowbit) {
        return ((((~0U<<highbit)^(~0U<<lowbit))|(1<<highbit))>>lowbit)<<lowbit;
    }
    [edit]

    But what is OU? There seems to be declaration or definition anywhere. Where does it come from?

  7. #7
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by cunnus88
    But what is OU? There seems to be declaration or definition anywhere. Where does it come from?
    It's not OU (oh-you), it's 0U (zero-you), which is a zero with type unsigned int -- with bits it's best to work with unsigned types.
    Quote Originally Posted by cunnus88
    I tried Dave's code as a lark, and it worked! (even when the highbit was 31)
    The first part of it is merely a condensed version of what you had. But an issue you were having was with the highbit + 1 going over the top. What you were doing, though, was making sure that the selected high bit was set. I did that explicitly.
    Quote Originally Posted by cunnus88
    So I take it that there is no way to shift that final most significant bit so that it becomes a 0?
    The part about making it zero if lowbit is greater than highbit is done by shifting the intermediate result right and then left by lowbit.

    Perhaps this may help.
    Code:
    #include <stdio.h>
    
    /*
    #define TEST
    */
    
    void bits_uint(unsigned int value)
    {
       unsigned int bit;
       for ( bit = /* msb */(~0U >> 1) + 1; bit > 0; bit >>= 1 )
       {
          putchar(value & bit ? '1' : '0');
       }
       putchar('\n');
    }
    
    #ifdef TEST
    int bitMask(int highbit, int lowbit)
    {
       return((((~0U<<highbit)^(~0U<<lowbit))|(1<<highbit))>>lowbit)<<lowbit;
    }
    #endif
    
    int bitMask_explained(int highbit, int lowbit)
    {
       unsigned int highbits, lowbits, result, msb;
    
       highbits = ~0U << highbit;
       fputs("highbits : ", stdout); bits_uint(highbits);
    
       lowbits = ~0U << lowbit;
       fputs("lowbits  : ", stdout); bits_uint(lowbits);
    
       result = highbits ^ lowbits;
       fputs("result   : ", stdout); bits_uint(result);
    
       msb = 1 << highbit;
       fputs("msb      : ", stdout); bits_uint(msb);
    
       result |= msb;
       fputs("result   : ", stdout); bits_uint(result);
    
       result >>= lowbit;
       fputs("result   : ", stdout); bits_uint(result);
    
       result <<= lowbit;
       fputs("result   : ", stdout); bits_uint(result);
       return result;
    }
    
    int main(void)
    {
       int hi, lo;
    #ifdef TEST
       unsigned int maxhi, maxlo;
       for ( maxlo = (~0U >> 1) + 1, lo = 0; maxlo; maxlo >>= 1, ++lo )
       {
          for ( maxhi = (~0U >> 1) + 1, hi = 0; maxhi; maxhi >>= 1, ++hi )
          {
             printf("hi = %2u, lo = %2u : %#x\n", hi, lo, bitMask(hi, lo));
          }
       }
    #endif
       hi = 5, lo = 3;
       printf("hi = %2u, lo = %2u : %#x\n", hi, lo, bitMask_explained(hi, lo));
       return 0;
    }
    
    /* my output
    highbits : 11111111111111111111111111100000
    lowbits  : 11111111111111111111111111111000
    result   : 00000000000000000000000000011000
    msb      : 00000000000000000000000000100000
    result   : 00000000000000000000000000111000
    result   : 00000000000000000000000000000111
    result   : 00000000000000000000000000111000
    hi =  5, lo =  3 : 0x38
    */
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  8. #8
    Registered User
    Join Date
    Oct 2005
    Posts
    271
    Thank you! That was definitely an eye-opener.

    The bits_uint function especially.

    However, defining an integer as unsinged was not an option I was looking for. I got the problems I was "twiddling" with off this site:

    http://www.cs.rochester.edu/u/scott/...ments/A1.shtml

    In it, one of the explicit restrictions is that:

    ...that you may only declare variables of type int...
    I guess that means the student will not be allowed to declare unsigned int. (I'm not a student by the way. Just somebody who was passing by and had his curiosity piqued. No ethical problems about helping out)

    Also, casting is not allowed.

    So in this set of problems, I should be working only with signed integers. And my original solution to the problem

    Code:
    	int i = 0, j = 0;
    	i = ~i;
    pegs the most significant bit as 1 which would block any operation such as
    Code:
    i <<= 32;
    Nonetheless, thank you very much for your comments. They really helped.

  9. #9
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by cunnus88
    The bits_uint function especially.
    Here's the whole family:
    Quote Originally Posted by cunnus88
    However, defining an integer as unsinged was not an option I was looking for.
    That's too bad. It's a poor idea to use signed integers.
    Quote Originally Posted by cunnus88
    In it, one of the explicit restrictions is that:
    ...that you may only declare variables of type int...
    Well, no variables were declared as unsigned. [edit]In fact, no variables were declared at all, other than the function parameters which were declared as ints.[/edit] [edit=2]Drop the U suffix if if bothers you.[/edit]
    Quote Originally Posted by cunnus88
    Also, casting is not allowed.
    Where do you see any casting?
    Quote Originally Posted by cunnus88
    Nonetheless, thank you very much for your comments. They really helped.
    Good to hear. Thank you.
    Last edited by Dave_Sinkula; 12-01-2005 at 11:06 PM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    1

    EZ Solution

    Code:
    // first a 32 entry table
    unsigned long maskArray[32] =
    {
      0xFFFFFFFF,
      0xFFFFFFFE,
      0xFFFFFFFC,
      0xFFFFFFF8,
      0xFFFFFFF0,
      0xFFFFFFE0,
      0xFFFFFFC0,
      0xFFFFFF80,
      0xFFFFFF00,
      0xFFFFFE00,
      0xFFFFFC00,
      0xFFFFF800,
      0xFFFFF000,
      0xFFFFE000,
      0xFFFFC000,
      0xFFFF8000,
      0xFFFF0000,
      0xFFFE0000,
      0xFFFC0000,
      0xFFF80000,
      0xFFF00000,
      0xFFE00000,
      0xFFC00000,
      0xFF800000,
      0xFF000000,
      0xFE000000,
      0xFC000000,
      0xF8000000,
      0xF0000000,
      0xE0000000,
      0xC0000000,
      0x80000000,
    };
    
    // then 1 line of code
    /*****************************************************************
           BITMASK
    ******************************************************************/       
    unsigned long bitMask (int highbit, int lowbit)
    {
      unsigned long retVal = maskArray[lowbit] & ~(maskArray[highbit] << 1);
      return retVal;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 09:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21