Design Puzzle: Detection of power of 2 number

Welcome to Design Puzzle. Here we will discuss an interview question:

Question: 

Derive the logical expression for a combinational digital circuit that accepts an 'n' bit input and produces a 1-bit output. The output will be 1 if the input number is a power of 2. Otherwise, produce output 0.

Approach:

This is a tricky question because we are accepting variable bits of input. Hence, we can't follow the standard procedure of creating a Truth Table for all the inputs and deducing the logic. 

We need to approach the problem with more of an intuitive thinking.

Analysis:

Let us list down the numbers in binary format that are powers of 2:

2: 'b10
4: 'b100
8: 'b1000
16: 'b10000

Anything that caught your eye? Well yes, there's only a single bit '1' in all of these numbers.

Let us perform one more step. Subtract 1 from the above numbers:

2 - 1 = 1: 'b01
4 - 1 = 3: 'b011
8 - 1 = 7: 'b0111
16 - 1 = 15: 'b01111

Now compare each number with its 1 subtracted value. Notice a pattern?

The single bit 1 has turned to 0 and all the preceeding 0s have flipped to 1s! 

Now the final step is easy.

Perform bitwise AND operation of the input and input -1. Then you will get all 0s. Now, OR all these bits to get a single bit output and invert it.

This will produce an output of '1' only for those numbers which are powers of 2.

Final logical expression : output = ! ( | ( input & input - 1 ) )