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
"Gebo" means to "give and take". This is my attempt to share the knowledge & experience with the community. Focus on Puzzles, Algorithms, Problem Solving, Java & other Technical Discussions.
6 comments:
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)
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
The question is same as finding whether a number is a power of 2 put in a different form
Test fails if there are no bits set
in your example
n = 0
n' = 0
k = 0
k == 0
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
N & (~N +1)
Post a Comment