Bits inverting

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

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.