How to invert the bits of a number?
Can anyone tell me most efficient way?
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
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.
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.
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.
I don’t think it has O(1) complexity, it should be O(logn).
Okay, my bad didn’t consider the most significant bit.