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