A number is a power of 2 when exactly one bit of its binary pattern is 1: 1, 2, 4, 8 and so on. So "is this 32-bit pattern a power of 2?" is the same question as "is exactly one bit set?". This post gives a Verilog module that answers it by counting the ones, then a smaller circuit that answers it with one subtraction and one AND.
Why you would need it
The check turns up more often in hardware than you might expect:
- One-hot checks. State machines with one-hot encoding, arbiter grant vectors and decoder outputs must have exactly one bit set. An assertion that the vector is a power of 2 catches a stuck or doubled grant.
- Configuration checks. Buffer sizes, cache line sizes and FIFO depths are often required to be powers of 2 so that address wrap is a simple mask.
- Alignment and divide shortcuts. If a divisor is a power of 2, division becomes a shift and modulo becomes an AND; the check decides which path to take.
How it works, in outline
There are two common ways to build it:
- Count the ones. Add up all 32 bits. If the total is exactly 1, the pattern is a power of 2. This is easy to read but builds an adder tree.
- Clear the lowest set bit. Subtracting 1 from a number flips its lowest 1 to 0 and all the 0s below it to 1. ANDing that with the original clears the lowest set bit. If nothing is left and the input was not zero, there was only one bit to begin with.
Both give the same answer. The first is the one in the original post; the second is usually smaller and faster.
The population count version
The module below adds every bit of data_in and flags a match when the sum is exactly 1. The sum is 6 bits wide because 32 ones need 6 bits (32 = 100000 in binary).
module pat_det ( data_in, patDetected );
input [31:0] data_in;
output patDetected;
wire [5:0] patSum = data_in[0] + data_in[1] + data_in[2] + data_in[3] +
data_in[4] + data_in[5] + data_in[6] + data_in[7] +
data_in[8] + data_in[9] + data_in[10] + data_in[11] +
data_in[12] + data_in[13] + data_in[14] + data_in[15] +
data_in[16] + data_in[17] + data_in[18] + data_in[19] +
data_in[20] + data_in[21] + data_in[22] + data_in[23] +
data_in[24] + data_in[25] + data_in[26] + data_in[27] +
data_in[28] + data_in[29] + data_in[30] + data_in[31] ;
wire patDetected = (patSum == 1) ? 1'b1 : 1'b0;
endmodule
The first version of this code listed data_in[20] twice and declared patSum as 5 bits. Both are corrected above; the deep dive shows what they broke.
The subtract-and-AND version
The same check in one line, from Sean Eron Anderson's Bit Twiddling Hacks, "Determining if an integer is a power of 2", written here in Verilog:
module pow2_det ( input wire [31:0] data_in,
output wire patDetected );
assign patDetected = (data_in != 32'd0) && ((data_in & (data_in - 32'd1)) == 32'd0);
endmodule
The zero test matters. Without it, an input of 0 passes, because 0 AND anything is 0. The same page notes that the plain form wrongly treats 0 as a power of 2.
Deep dive: the numbers and details
This part holds worked bit patterns, the width and duplicate-bit bugs in the first version, and a comparison of the two circuits. Skip it if the overview is all you need.
Worked examples of the subtract-and-AND test
| data_in (8 bits shown) | data_in - 1 | AND | Non-zero input? | Result |
|---|---|---|---|---|
| 0010 0000 (32) | 0001 1111 | 0000 0000 | Yes | Power of 2 |
| 0010 1000 (40) | 0010 0111 | 0010 0000 | Yes | Not a power of 2 |
| 0000 0001 (1) | 0000 0000 | 0000 0000 | Yes | Power of 2 (20) |
| 0000 0000 (0) | 1111 1111 | 0000 0000 | No | Not a power of 2 |
The second row shows why it works: subtracting 1 only touches the lowest 1 and the zeros below it, so any higher 1 survives the AND.
What the duplicated bit 20 did
With data_in[20] added twice, the sum counts bit 20 as two ones. Two inputs show the effect:
32'h0010_0000(only bit 20 set, which is 220): the sum is 2, so the old module said "not a power of 2". That is a missed detection.32'hFFFF_FFFF(all 32 bits set): the true count is 32, but the old sum is 33.
What the 5-bit sum did
In Verilog, the width of an addition in a continuous assignment is set by the widest operand and the left-hand side, so a 5-bit patSum makes every partial sum 5 bits and the result wraps modulo 32. Combined with the duplicated bit, the all-ones input gives 33 mod 32 = 1, and the old module flagged 32'hFFFF_FFFF as a power of 2. With the duplicate removed, 32 ones give 32 mod 32 = 0, which happens to be harmless, but a 6-bit sum states the intent and survives later edits.
Comparing the two circuits
| Population count | Subtract and AND | |
|---|---|---|
| Main logic | Adder tree over 32 one-bit inputs, then compare with 1 | 32-bit decrement, 32 AND gates, two zero detects |
| Logic depth | About log2(32) = 5 adder levels plus the compare | Decrement borrow chain plus a 32-input OR tree |
| Also gives | The number of ones, useful for other checks | Only the yes or no answer |
| Typical use | When the count is needed anyway | One-hot checks and assertions |
A third form, common in assertions, avoids arithmetic entirely: a vector is one-hot when it is non-zero and no two bits are set together. SystemVerilog has a built-in for it, $onehot(data_in), and $onehot0 also allows all zeros.
Common mistakes
- Forgetting the zero case in the subtract-and-AND form.
- Making the sum too narrow, so it wraps. A count of N bits needs ceil(log2(N+1)) bits: 6 bits for 32 inputs, 7 bits for 64.
- Typing a long sum by hand and repeating or skipping a bit, as happened here. A loop or a reduction is safer:
integer i;
reg [5:0] cnt;
always @* begin
cnt = 6'd0;
for (i = 0; i < 32; i = i + 1)
cnt = cnt + data_in[i];
end
Interview angle
"Detect whether a 32-bit value is a power of 2" is a common screening question. A strong answer gives the v && !(v & (v - 1)) form, explains why subtracting 1 clears the lowest set bit, mentions the zero case, and notes that in hardware it is the same as a one-hot check.
Further reading
- Bit Twiddling Hacks: determining if an integer is a power of 2
- Bit Twiddling Hacks: counting bits set, Brian Kernighan's way, which uses the same clear-the-lowest-bit step


module pat_det ( data_in, patDetected );
ReplyDeleteinput [31:0] data_in;
output patDetected;
wire [31:0] Get_ones = data_in[31:0] | (data_in[31:0] - 1'b1)
assign patDetected = !(&Get_ones[31:0]);
endmodule
For the wire statment, shouldn't that be "&" instead of "|" ?
ReplyDelete