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
skip to main |
skip to sidebar
"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.
About Me
Search Gebo
Share & Subscribe
Books & Knowledge Base @ Amazon
Links
|
| Buttons reused from http://www.webfruits.it/freebies.htm and http://mysocialbuttons.com/ |
Archive
-
▼
2009
(26)
-
▼
August
(13)
- ping.fm - better than friendfeed, just what I want
- Rope Escape
- [ALGO] Six Colored Balls
- svn:ignore
- Find if there is only one bit set in a number
- [PS] Catch the Fox
- Algorithms from "100 Interview Questions for Softw...
- All purpose problem solving algorithm
- [ALGO] Water jugs problem
- Find if number occurs exactly n/2 times in an array
- Dividing array into groups
- Sort on second key when, first key in a set is sorted
- Find if summation of numbers from two lists is giv...
-
▼
August
(13)
Labels / Tag
algorithms
(15)
amazon
(3)
antivirus
(1)
arithmetic series
(1)
array
(5)
backtracking
(1)
bash
(1)
basics
(1)
binary trees
(1)
brindavan garden
(1)
bulb
(1)
C++
(1)
callback
(1)
clam
(1)
clamav
(1)
clock
(1)
CLRS
(2)
cormen
(3)
data structures
(1)
duplicate
(1)
easymock
(1)
education
(1)
excel
(1)
freshclam
(1)
hanoi
(1)
hashing
(1)
httpclient
(1)
humor
(1)
induction
(1)
interview question
(9)
irrational
(1)
Java
(5)
jmockit
(1)
learning
(1)
level_easy
(1)
linux
(3)
logger
(1)
macro
(1)
madhur
(2)
mathematics
(5)
matrix
(1)
microsoft
(6)
mock
(2)
mockito
(2)
mysore
(1)
networking
(1)
OCW
(1)
odd man out
(1)
oocalc
(1)
OOTB
(1)
pattern
(1)
Persistent
(1)
probability
(2)
problem
(1)
problem solving
(17)
proxy
(1)
proxy selector
(1)
puzzle
(5)
quote
(1)
randomized
(1)
recurrsion
(2)
repeating
(1)
resolution
(1)
reverse
(1)
riddle
(5)
road trip
(1)
script
(1)
search
(2)
shell
(1)
shell script
(1)
socks
(1)
solaris
(1)
solved
(1)
sort
(3)
stock
(1)
strategy
(1)
subversion
(1)
summation
(1)
svn
(1)
switch
(1)
tanwani
(2)
TDD
(2)
technology
(2)
theorem
(1)
timer
(1)
todo
(1)
travel
(1)
trees
(1)
tutorial
(1)
unimodal
(1)
unit test
(2)
walk the bridge
(1)
warmup
(1)
water jugs
(1)
windows
(1)
xkcd joke
(1)
© Madhur Kumar Tanwani
All material on this page, is free to use as long as references to the original source is maintained and credits are given to this website as one of the sources. Few clicks on the Ads on this page will help too :)
All material on this page, is free to use as long as references to the original source is maintained and credits are given to this website as one of the sources. Few clicks on the Ads on this page will help too :)
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