Find if there is only one bit set in a number

In the bit representation of a number, find if there is exactly one bit that is set.

e.g. your approach should say true for the following numbers :
1,2,4,8,16
and false for the following numbers :
3,5,7,10

6 comments:

Madhur Kumar Tanwani said...

We can use the 2 complements method to find this.

- Let number be n
- Take 2's complement of n. Let this be n'
- BITWISE AND n and n'. Let this result be k
- if k == n, then n has exactly one '1' bit

e.g. Let number of '8'
n = 8 (....01000)
n' = ....11000
k = 8 (....01000)


e.g. Let number of '10'
n = 10 (....01010)
n' = ....10110
k = 2 (....00010)

Madhur Kumar Tanwani said...

Working code :

public class ExactlyOneBitInNumber {
public static void main(String[] args) {
int i = 8;
int j = -(i);
System.out.println(" i = " + i);
System.out.println(" j = " + j);

int k = (i & j);
System.out.println(" k = " + k);

System.out.println();

i = 10;
j = -(i);
System.out.println(" i = " + i);
System.out.println(" j = " + j);

k = (i & j);
System.out.println(" k = " + k);
}
}

O/P :
i = 8
j = -8
k = 8

i = 10
j = -10
k = 2

Tom Praison said...

The question is same as finding whether a number is a power of 2 put in a different form

Anonymous said...

Test fails if there are no bits set

in your example
n = 0
n' = 0
k = 0
k == 0

Madan Kumar said...

Take any random number which is a power of 2. Its binary can be shown as (0*)1(0*). Its complement will be (1*)0(1*). If I add 1 to it, it will become (1*)1(o*)
i.e. XXXX01111 + 1 = XXXX10000

So, finally if you XOR this number with the actual number, you will get the same number again.

That is the check you should do
ie. x ^ (x` + 1) == x.
Note that it will not hold for x=0. You should special case it

Ravi said...

N & (~N +1)

 
Stats