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?

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.

Ugly and cryptic for amusement only:

Code:

int bitMask(int highbit, int lowbit) {
    return ((((~0U<<highbit)^(~0U<<lowbit))|(1<<highbit))>>lowbit)<<lowbit;
}

[edit]Oops.

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.

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.

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

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)

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?

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.

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.

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
*/

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.

Originally Posted by cunnus88

The bits_uint function especially.

Here's the whole family:

• Part I
• Part II
• Part III (not well liked, apparently)

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.

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]

Originally Posted by cunnus88

Also, casting is not allowed.

Where do you see any casting?

Originally Posted by cunnus88

Nonetheless, thank you very much for your comments. They really helped.

Good to hear. Thank you.

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;
}