How to invert the bits of a number?
Can anyone tell me most efficient way?
XOR of a number with 1 inverts the bit…for eg: if you have 1001 as binary representation of a decimal then XOR of this with 1111 gives the required answer.
1001^1111=0110. 5^15 = 6
5 Likes
Just adding to Adhish Kapoor’s great answer:
If you have the number “n” in decimal, you need the number “xn” (with equivalent number of bits of 1) to XOR with.
You can use i=(int)ceil(log2(n)) to find the number of bits. Then 2^i-1 will give you xn.
For n=9(1001), i=ceil(log2(9))=4, so xn=2^4-1=15(1111), now you can XOR them easily.
1 Like
Probably the best way to invert bits of a specific nimber is ~n, it’ll convert all 0’s in a number to 1 and 1 to 0.
It has O (1) complexity because you don’t need to calculate the number of 1’s and then apply XOR operatpr.
1 Like
I don’t think it has O(1) complexity, it should be O(logn).
If you want to invert ith bit, simply use n ^ (1 < < i). For long long value, use n ^ (1LL < < i).
For inverting all bits, you can use method given by @theintel.
In @neilit1992 answer, all bits are inverted, including the most significant bit which denotes whether the number is positive or negative. That’s why you get negative number.
Okay, my bad didn’t consider the most significant bit.