Bitwise operations logical task

Question

I think about this problem many hours already, but solution doesn't want to come. Maybe someone have any ideas?

The question is:

 "Using ONLY bitwise operators, write the function that sets 
  the leftmost zero bit to one" 

Conditions - prohibited
Recursion - prohibited
Loops - prohibited
Arithmetic operations - prohibited

Example:

Input: 11010010

Output: 11110010

P.S. Input actually should be unsigned int, but for simplicity let this be as binary, it is mere details.

score 2 · Accepted Answer · answered Jul 27 '13 at 12:09

You can propagate the leftmost zero to the right like this:

x &= x >> 1;
x &= x >> 2;
x &= x >> 4;
// etc

In the example, you'd get 11000000

Then if you invert that, you get a mask of ones up to and including the leftmost zero, in this example, 00111111

Then you can isolate the leftmost one (which, by construction, is at the same position as the leftmost zero in the input) in that easily with x ^ (x >> 1)

Just OR that into the input.

Putting it together: (not tested)

uint32_t y = x;
x &= x >> 1;
x &= x >> 2;
x &= x >> 4;
x &= x >> 8;
x &= x >> 16;
x = ~x;
return y | (x ^ (x >> 1));

There may be a simpler solution

score 0 · Answer 2 · edited May 23 '17 at 12:23

0

After some time came to the similar solution as harold suggested, but with few improvements. Here is the code

unsigned long int getLastZeroPosition(unsigned long int value)
{
   unsigned long int temp = ~value;
   temp = temp | temp >> 1;
   temp = temp | temp >> 2;
   temp = temp | temp >> 4;
   temp = temp | temp >> 8;
   temp = temp | temp >> 16;
   temp = temp | temp >> (sizeof(unsigned long int) << 2);  // handles x86/x64

   temp = temp >> 1;
   temp = (~temp) & (~value);
   return temp;
}

edited May 23 '17 at 12:23

Community

1
1

answered Jul 31 '13 at 08:35

Ikakok

103
1
10

No need for temp |= temp >> 64, because before this line i already did shift for 31 (1 + 2 + 4 + 8 + 16). So in case 32-bit it is already enough and any other shift will take no effect. But if it is x64 then it will additionally shift for 32 (sizeof(ui) << 2 = 8 << 2 = 32). And in summary it will shift for 63. – Ikakok Aug 01 '13 at 08:09

score 0 · Answer 3 · edited May 23 '17 at 11:50

I will assume that I can implement using Java. If you change the question to "Using ONLY bitwise operators, write the function that sets the RIGHTMOST zero bit to one", then you can solve the problem as follows:

int a = 0b1111_1111_1111_1111_1111_1101_0110_1111;
a = a | (a & (a^(a+1)))+1;
System.out.println(Integer.toBinaryString(a));

This answer is the mirror of what we need, so simply mirror the input first:

int a = 0b1111_1111_1111_1111_1111_1101_0110_1111;
a = Integer.reverse(a);
a = Integer.reverse(a | (a & (a ^ (a + 1))) + 1);
System.out.println(Integer.toBinaryString(a));

But of course, using one Java built-in (reverse), gives you the right to use the other (highestOneBit) too:

int a = 0b1111_1111_1111_1111_1111_1101_0110_1111;
a = Integer.highestOneBit(~a)+a;
System.out.println(Integer.toBinaryString(a));

If you want to implement your own reverse using basic bitwise operators, and possibly implement in c, that is possible too: Reverse bits

Bitwise operations logical task

3 Answers3