Algorithms from "100 Interview Questions for Software Developers" : Part 1

Q1. How do you find out if a number is a power of 2?
Q2. And how do you know if it is an odd number?

6 comments:

Madhur Kumar Tanwani said...

Assumption : Number is an integer

Q2. And how do you know if it is an odd number?

- Check the LSB of the number.
- If the bit is '1' the number is odd.
- If the bit is '0' the number is even.

Checking for 1st bit can be implemented as a BITWISE AND operation of the number with 0x1

Madhur Kumar Tanwani said...

Assumption : The number is an integer

Q1. How do you find out if a number is a power of 2?

A number is a power of 2, if it satisfies these conditions :
1. it is not odd
2. there is only one bit set in the number (and it is not the LSB - first condition)

We have already solved how to check for the first condition (see 1st comment to this blog)

2nd condition is solved in another blog entry here : http://madhurtanwani.blogspot.com/2009/08/find-if-there-is-only-one-bit-set-in.html

emptee said...

"Q1. How do you find out if a number is a power of 2?

A number is a power of 2, if it satisfies these conditions :
1. it is not odd
2. there is only one bit set in the number (and it is not the LSB - first condition)"

First condition is not necessary.

1 is power of 2, 2^0 = 1

Madhur Kumar Tanwani said...

@emptee
You are right. How could I be so dumb :(

Tom Praison said...

Q1. Can also be solved in this fashion also
return (n-1 & n) ==0);

Consider n=4 ie. 100 in bin
n-1 will be all 1's but a digit lesser than n 11. doing a & with n will give 0. This condition hold good only for those numbers which are powers of 2

emptee said...

@Tom

Tom your solution is essentially a practical step of above solution given by madhur. Does there exist a different (purely mathematical and no messing with bits) solution?

 
Stats