How 
can
 you
 determine
 whether
 a
 number
 is 
a
 power
 of 
2 efficiently?

Solution

Check
 whether 
x
 & (x
‐
1) 
is 
0.

 If
 x 
is
 not
 an 
even
 power
 of
 2,
 the
 highest 
position 
of 
x
 with 
a
 1
 will 
also 
have
 a
 1 
in
 x
‐
1;
 otherwise,
 x
 will 
be
 100...0
 and
 x
‐
1
 will 
be 
011...1; 
and'ing
 them 
together 
will
 return 
0.

Source -  http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_3.pdf

Share this thread

Comments

Comments
comments powered by Disqus

Navigation

Social Media