CODEWITHSUNDEEP
bit-manipulationbitwise-operatorsbit
Ikakok
Ikakok

Reputation: 103

Bitwise operations logical task

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.

Upvotes: 1

Views: 354

Answers (3)

YoYo
YoYo

Reputation: 9415

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

Upvotes: 0

Ikakok
Ikakok

Reputation: 103

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

Upvotes: 0

user555045
user555045

Reputation: 64913

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

Upvotes: 2

Related Questions