# Determine whether a binary number is of power of two in verilog code

1. ## Determine whether a binary number is of power of two in verilog code

I am trying to determine whether a binary number is of power of two (in other words, is it of one-hot encoding).

I found a method to do so, but it is for integer.

Could anyone help to transform the method for usage with binary number in verilog ?   Reply With Quote

•

2. ## Re: Determine whether a binary number is of power of two in verilog code

Without thinking too hard early on a Monday morning, I think this could be done with a bunch of cascaded XORs. Output would be logic 1 if only one bit is set. Exception: is zero a power of 2?  Reply With Quote

3. ## Re: Determine whether a binary number is of power of two in verilog code

@barry - I was going to say that , but it doesnt work.

1011:

1 XOR 0 = 1 XOR 1 = 0 XOR 1 = 1

So you dont get a power of 2.  Reply With Quote

4. ## Re: Determine whether a binary number is of power of two in verilog code

See the verilator linting output with is_power_of_two.v

Code:
```verilator -Wall --lint-only is_power_of_two.v
%Warning-WIDTH: is_power_of_two.v:6: Logical Operator LOGAND expects 1 bit on the LHS, but LHS's VARREF 'v' generates 8 bits.
: ... In instance is_power_of_two
always @(*) f = v && !(v & (v - 1));
^~
... Use "/* verilator lint_off WIDTH */" and lint_on around source to disable this message.
%Warning-WIDTH: is_power_of_two.v:6: Logical Operator LOGNOT expects 1 bit on the LHS, but LHS's AND generates 32 or 8 bits.
: ... In instance is_power_of_two
always @(*) f = v && !(v & (v - 1));
^
%Warning-UNUSED: is_power_of_two.v:4: Signal is not used: 'f'
: ... In instance is_power_of_two
reg f;
^
%Error: Exiting due to 3 warning(s)
%Error: Command Failed /usr/bin/verilator_bin -Wall --lint-only is_power_of_two.v```
```Code Verilog - [expand]1
2
3
4
5
6
7
8
module is_power_of_two();

reg [7:0] v = 8'b11110000;
reg f;

always @(*) f = v && !(v & (v - 1));

endmodule```  Reply With Quote

•

5. ## Re: Determine whether a binary number is of power of two in verilog code Originally Posted by TrickyDicky @barry - I was going to say that , but it doesnt work.

1011:

1 XOR 0 = 1 XOR 1 = 0 XOR 1 = 1

So you dont get a power of 2.
I told you it was early in the morning!  Reply With Quote

6. ## Re: Determine whether a binary number is of power of two in verilog code

Cascaded XOR is a parity generator.

In Verilog the code looks exactly the same as the C example.

```Code Verilog - [expand]1
2
logic [3:0] v;
assign f = v && !(v & (v -1));```

Though I prefer using a reduction NOR (~|) instead of the ! as the logic is trying to detect the all 0 condition, which is easily done by a reduction NOR operation instead of a logical NOT.

The whole point of the v & (v -1) is to find any values that result in a bitwise ANDing of the values resulting in all zeros, which incidentally only happens on powers of 2 or when the value is 0.

```Code Verilog - [expand]1
2
3
4
5
6
7
8
9
10
11
12
13
14
module not_test;

logic [3:0] v;
logic [3:0] vm1;

initial begin
for (int i=0; i<16; i++) begin
v = i;
\$display ("v=%4b,  v-1=%4b,  v&(v-1)=%4b,  !(v&(v-1))=%4b,  v&&!(v&(v-1))=%4b,  v&&~|(v&(v-1))=%4b", v, v-4'b1, v&(v-4'b1), !(v&(v-4'b1)), v&&!(v&(v-4'b1)), v&&~|(v&(v-4'b1)));
end
\$stop;
end

endmodule```
Here is a simple test if you want to try it out for yourself.

test run results in the following:
Code:
``` v=0000,  v-1=1111,  v&(v-1)=0000,  !(v&(v-1))=0001,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=0001,  v-1=0000,  v&(v-1)=0000,  !(v&(v-1))=0001,  v&&!(v&(v-1))=0001,  v&&~|(v&(v-1))=0001
v=0010,  v-1=0001,  v&(v-1)=0000,  !(v&(v-1))=0001,  v&&!(v&(v-1))=0001,  v&&~|(v&(v-1))=0001
v=0011,  v-1=0010,  v&(v-1)=0010,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=0100,  v-1=0011,  v&(v-1)=0000,  !(v&(v-1))=0001,  v&&!(v&(v-1))=0001,  v&&~|(v&(v-1))=0001
v=0101,  v-1=0100,  v&(v-1)=0100,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=0110,  v-1=0101,  v&(v-1)=0100,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=0111,  v-1=0110,  v&(v-1)=0110,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=1000,  v-1=0111,  v&(v-1)=0000,  !(v&(v-1))=0001,  v&&!(v&(v-1))=0001,  v&&~|(v&(v-1))=0001
v=1001,  v-1=1000,  v&(v-1)=1000,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=1010,  v-1=1001,  v&(v-1)=1000,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=1011,  v-1=1010,  v&(v-1)=1010,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=1100,  v-1=1011,  v&(v-1)=1000,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=1101,  v-1=1100,  v&(v-1)=1100,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=1110,  v-1=1101,  v&(v-1)=1100,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000
v=1111,  v-1=1110,  v&(v-1)=1110,  !(v&(v-1))=0000,  v&&!(v&(v-1))=0000,  v&&~|(v&(v-1))=0000```  Reply With Quote

•

7. ## Re: Determine whether a binary number is of power of two in verilog code

The solution is to use

Code:
`always @(*) f = (v != 0) && ((v & (v - 1)) == 0);`

Someone suggested me to use power_of_two = ^v which is so much simpler.

Any comment ?  Reply With Quote

8. ## Re: Determine whether a binary number is of power of two in verilog code

The solution is to use
Code:
`always @(*) f = (v != 0) && ((v & (v - 1)) == 0);`
No necessarily the only possible way to describe it, but clear and unequivocal Verilog, in so far preferred.

Someone suggested me to use power_of_two = ^v which is so much simpler.
How exactly? I don't think it's possible, but why don't you try?  Reply With Quote

9. ## Re: Determine whether a binary number is of power of two in verilog code Originally Posted by promach The solution is to use

Code:
`always @(*) f = (v != 0) && ((v & (v - 1)) == 0);`
No it's not the preferred solution, it is a verbose solution. Maybe you should switch to VHDL.
Since you ignored my post, I'll just assume you have me on your ignore list.... Originally Posted by promach Someone suggested me to use power_of_two = ^v which is so much simpler.

Any comment ?
Yeah my comment is, don't listen to them they don't know much. ^v is reduction XOR which is how you compute PARITY it does not compute powers of 2. I already mentioned that in my previous post #6.  Reply With Quote

10. ## Re: Determine whether a binary number is of power of two in verilog code

The following will also work, with less LUTs and higher fmax compared to the solution above.

```Code Verilog - [expand]1
always @(*) is_power_of_two = ((in + in + in + in + in + in + in + in) == 1);```  Reply With Quote

11. ## Re: Determine whether a binary number is of power of two in verilog code

Yes, but it assumes but it has the following limitations:
1. It doesnt allow for In = 0 (2^0)
2. It is always 8 bits.
The previous case covered the 0 case and allowed for any length of bits  Reply With Quote

12. ## Re: Determine whether a binary number is of power of two in verilog code

The performance difference is nevertheless remarkable, at least with Quartus tool. The capability of a synthesis tool to find optimal solutions can't be predicted, you need to try.

I can write a parameterizable solution in VHDL with the same performance as the post #10 code, but I didn't succeed in Verilog.

```Code VHDL - [expand]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity test is
generic
(
DATA_WIDTH : natural := 8
);
port
(
inp    : in std_logic_vector(DATA_WIDTH-1 downto 0);
result : out std_logic
);
end entity;

architecture rtl of test is
begin
process (inp)
variable n: integer;
begin
n := 0;
for i in 0 to data_width-1 loop
n := n + to_integer(unsigned(inp(i downto i)));
end loop;
result <= '0';
if n=1 then result <= '1'; end if;
end process;
end rtl;```

The RTL schematic shrinks down to gate level  1 members found this post helpful.  Reply With Quote

•

13. ## Re: Determine whether a binary number is of power of two in verilog code Originally Posted by promach The following will also work, with less LUTs and higher fmax compared to the solution above.

```Code Verilog - [expand]1
always @(*) is_power_of_two = ((in + in + in + in + in + in + in + in) == 1);```

Interesting that you are pointing this out to me as if I don't already know this solution. I have been discussing the question posted in #1 and the desire to translate it to Verilog. I was also commenting about how you cannot use a reduction XOR operation to check for power of two.

If you wanted to discuss optional ways of doing this I would have suggested using a simple add up all the bits, which is typically the easiest way to determine if only a single bit is set. The adding bits method does not require the bit width wide add operation as required by the post #1 algorithm (which is probably where most of the resulting performance hit issue comes from). Though to correctly deal with finding a power of two, you need to modify the above logic by not adding bit-0 and ANDing the entire addition result with the inverse of bit-0 (i.e. if bit-0 is 1 then the input is odd and the result should be 0).
e.g.
```Code Verilog - [expand]1
assign is_power_of_two = ((in + in + in + in + in + in + in) == 1) & ~in;```  Reply With Quote

14. ## Re: Determine whether a binary number is of power of two in verilog code

20 = 1

So, in could have the value of 1

Note: I am trying to detect one-hot as mentioned in post #1  Reply With Quote

15. ## Re: Determine whether a binary number is of power of two in verilog code Originally Posted by promach 20 = 1

So, in could have the value of 1

Note: I am trying to detect one-hot as mentioned in post #1
Ah, sorry I was thinking you wanted power of 2 but not power of 2^0 for some reason (probably because of Tricky's comment). Never mind then extra & ~in then your original post will correctly compute a 1-hot bit (where 1 bit has to be hot).  Reply With Quote

--[[ ]]--