Monday, October 4, 2010

BIT Hacks

Write a single line of code for the below operations

1. Set the nth bit to 1.
x = x | (1 << n);

2. Reset the nth bit of number
x = x & ~(1 << n);

3. Toggle the nth bit of the number.
x = x ^ (1 << n);

4. Convert the (right adjusted) n-bit field of x that begins at position p x =(x >> (p+1-n)) & ~(~0 << n);

An important point to note is that none of your operation should overflow the variable in use.

Sunday, October 3, 2010

Given a number is power of 2?

Write 1 line code to find whether a number is a power of 2 or not?

Approach:
To clear the rightmost bit of a number the below utility can be used
n = n & (n-1) (Since n-1 turns off the right most bit and turns on all the bit lower than the rightmost bit)

Now to find the number is power of 2 or not is trivial
if n & (n-1) == 0
but there is a catch for the number of 0 :)
so a simple one liner code will be
return n && !(n & (n - 1));

Count the number of ways .

Lets start with a simple but a tricky one :)

You have n number of chocolates. Your best friend asks for the chocolate but you say that he can take only 1 or maximum 2 chocolates at a time.
Find the number of ways in which your friend can take all the chocolates in any number of times.

Approach :


The first thing to note is that how can you take n chocolates ?
Before having n chocolates you need to have either n-1 or n-2 chocolates (as you can only pick 1 or 2 chocolates).

So if f(n) denotes the number of ways to pick n chocolates then
f(n) = f(n-1) + f(n-2)
Wow it turns out to be a Fibonacci series !!!
Base cases you can work it out  :)

Try the extension of this problem here

Welcome Everybody

Well this is the the first post of this blog. This blog will provide myraid number of programming puzzles often useful in interviews in many top software companies. This blog will provoke to think differently and logical bend of mind. Will try to cover the standard as well as the variations of the programming questions.
The aim of of the blog will not be to provide the straightforward answers but to have a discussion and know various approaches to the problem(and also some of the wrong approaches :P)

Last but not the least any suggestions, comments or feedback are welcomed. Also if if you wish to contribute something to this blog or any concerns then you can reach me at aviral.nit@gmail.com

Happy browsing !!!