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

Status
Not open for further replies.
P

promach

Advanced Member level 4
Joined
Feb 22, 2016
Messages
1,199
Helped
2
Reputation
4
Reaction score
5
Trophy points
1,318
Activity points
11,636
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 ?

 

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?
 

@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.
 

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
 

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
 

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 ?
 

The solution is to use
Code: 
always @(*) f = (v != 0) && ((v & (v - 1)) == 0);
Click to expand...
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.
Click to expand...
How exactly? I don't think it's possible, but why don't you try?
 

promach said:
The solution is to use

Code: 
always @(*) f = (v != 0) && ((v & (v - 1)) == 0);
Click to expand...
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....

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

Any comment ?
Click to expand...
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.
 

@ads-ee

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[7] + in[6] + in[5] + in[4] + in[3] + in[2] + in[1] + in[0]) == 1);



Please correct me if wrong.
 

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
 

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



 
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[7] + in[6] + in[5] + in[4] + in[3] + in[2] + in[1]) == 1) & ~in[0];
 

20 = 1

So, in[0] could have the value of 1

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

promach said:
20 = 1

So, in[0] could have the value of 1

Note: I am trying to detect one-hot as mentioned in post #1
Click to expand...

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[0] then your original post will correctly compute a 1-hot bit (where 1 bit has to be hot).
 

Status
Not open for further replies.

Similar threads

Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…