2

Given a integer number, n. What is the fastest way to inverse bits of that number? For example, if n = 5 (101) then output should be 2(010). Prefix 0 aren't considered for inverse. The unique part of this question is that here, we don't consider prefix 0.

My approach:

Convert n to binary as a string. For example, if n = 5 then I'll have string, say str, as `101`.
Convert 1 to 0 and 0 to 1 in the string. (output: 010)
Convert resultant binary string to number. (output: 2)

More input/output examples:

Input: 7, Output: 0
Input: 8, Output: 7
Input: 10, Output: 5
Input: 98, Output: 29

As you can see, my approach looks naive or very inefficient. Is there a better way, by using some bit manipulation operation or any other way get desired output faster?

Note: n can be negative as well! For negative number, 2's compliment has to be taken in to account for inverting the bits.

I'm not asking for exact code. Pseudo code or approach will be helpful.

Abhishek
  • 6,912
  • 14
  • 59
  • 85
  • @IVlad `~n` will not work.. I tried it in C# (`uint n = 98;Console.WriteLine(~n);`//output 4294967197) and output wasn't `29`. Probably it will do something to signed bit :| – Abhishek May 19 '15 at 12:01
  • possible duplicate of [Bitwise operator for simply flipping all bits in an integer?](http://stackoverflow.com/questions/6351374/bitwise-operator-for-simply-flipping-all-bits-in-an-integer) – kiranpradeep May 19 '15 at 14:26
  • You must specify what to do with negative numbers, we can't read your mind. –  May 19 '15 at 15:30
  • It should basically do the same thing. If number is negative then it should inverse it's 2's complement bits – Abhishek May 19 '15 at 15:44
  • What about the sign bit ??? What about the 0 prefix ? –  May 19 '15 at 15:56
  • I've said about 0 prefix has to be ignored. In 2's compliment, does sign bit matter? :) – Abhishek May 19 '15 at 16:07
  • So you want to take 1's complement of a 2's complement negative number? – beaker May 19 '15 at 16:26
  • 2's compliment. Editing question to make things clear :) – Abhishek May 19 '15 at 16:30
  • Not clear. You want 2's complement in one case and 1's complement in another. Please give a concrete example of what you expect for both a positive number and a 2's complement negative number. – beaker May 19 '15 at 16:32
  • I want inversion of bits when number is positive. When number is negative, take 2's compliment and then invert it's bits. David's solution is working for me. I'm waiting for better performance solution. :) – Abhishek May 19 '15 at 16:33
  • Thank you. That was clearer. – beaker May 19 '15 at 16:35
  • Your first comment shows an implicit assumption about the "length" of the binary representation of a number (7 bits for 92?): please make that explicit, *especially* for negative numbers. (What do you display as a negative input, anyway?) – greybeard May 19 '15 at 21:45
  • I don't want prefix zeroes to be considered for positive numbers. .Hence you have 7 bits for 92. I want inversion of bits when number is positive. When number is negative, take 2's compliment and then invert it's bits. David's solution is working for me. I'm waiting for better performance solution. :) – Abhishek May 20 '15 at 02:12

5 Answers5

2

This problem is interreducible (with the overhead of a bitwise XOR instruction) with the problem of rounding n up to the least number of the form 2^k-1. For a 32-bit int n, you can adapt one of the standard bithacks for the latter:

m = n;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
return m ^ n;
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
1
unsigned reversed = 0;
while (num := 0) {
  reversed = reversed << 1;
  reversed |= (num & 1);
  num = num >> 1;
}

Shift low order bits out of the original, and or then shift them into successively higher bits in the reversal.

Ron Kuper
  • 817
  • 5
  • 14
  • Not working. Coded it in c# and for input 7, it gave output as 14. It wasn't expected :| – Abhishek May 19 '15 at 12:05
  • This appears to reverse the bit string of a number, rather than invert the bits, which is what the question is asking for (unless I'm mistaken). – davmac May 19 '15 at 16:34
1

flip(n) = 2^(ceiling(lg(n))) - 1 - n, where lg is log base 2.

If you know the max set bit of n, then you can quickly get 2^ceiling(lg(n)) by getting the max set bit and shifting 1 to the left by one more.

Dave
  • 7,460
  • 3
  • 26
  • 39
  • So, does `2^ceiling(lg(n))` give max set bit? – Abhishek May 21 '15 at 04:47
  • @Abhishek It gets you the max set bit if n is a power of 2; otherwise it gives you the next higher bit because of the ceiling function. E.g., lg(4)=2, lg(8)=3, so ceil(lg(5)) = ceil(lg(6)) = ceil(lg(7)) = ceil(lg(8)) = 3, and 2^3 = 8 = 1000 in binary. – Dave May 21 '15 at 11:32
  • If n is a power of 2 and you're getting 2^ceiling(lg(n)) via the max set bit, you don't shift, and instead just use 2^ceiling(lg(n)) = 2^lg(n) = n. E.g., if n=8 then n is 1000 in binary and n-1 = 7 = 111, as desired. – Dave May 21 '15 at 11:34
  • If n is 8, then `2^(ceiling(lg(n)))` is 8. Now, flip(8) = 8 - 1 - 8 = -1. But intended result was 7. How do you handle this scenario? – Abhishek May 21 '15 at 13:28
  • Right you are. Max set bit shifted left 1 will always work. You can take 2^(ceiling(lg(n | 1))) if you want a hacky way to avoid a problem when you're given a power of 2. Alternatively, if n is a power of 2 then n-1 is the answer without doing any work. – Dave May 21 '15 at 19:54
  • Awesome!! Now, next question would be, how do I quickly decide (without changing time complexity of problem) if n is a power of 2 or not? – Abhishek May 22 '15 at 04:46
  • 2
    The Bit Twiddling hacks page has a couple algorithms to find the max set bit in O(lg(k)) operations, where k is the number of bits of n (including leading zeroes). The rest is constant time. http://graphics.stanford.edu/~seander/bithacks.html – Dave May 22 '15 at 11:43
0

If performance really matters, you can tabulate.

Process the integer byte by byte from MSB to LSB. If the byte is null, skip. Otherwise use a precomputed lookup table of 256 entries (with prefix), and for the following bytes, XOR.

if (B[0]) { B[0]= LUT[B[0]]; B[1]^= 255; B[2]^= 255; B[3]^= 255; }
else if (B[1]) { B[1]= LUT[B[1]]; B[2]^= 255; B[3]^= 255; }
else if (B[2]) { B[2]= LUT[B[2]]; B[3]=^255; }
else B[3]= LUT[B[3]];

You can also XOR on 32 bits in a single go, with appropriate masks.

0

The reason that ~n didn't give you the expected results is all of the leading zeros in your number. To mask those zeros after they are inverted to ones, the straightforward way is:

m = abs(n);
result = ~m & (int)(exp2(ceil(log2(m)))-1);

This generates a mask of the correct length by taking the base-2 log of the (positive) input. Boundary cases where n is a power of 2 are correct because the leading 1 will always be 0 in the result, so its exclusion from the mask doesn't matter.

Performance is probably fair, but coding is concise.

beaker
  • 16,331
  • 3
  • 32
  • 49