+ Post New Thread
Results 1 to 15 of 15
  1. #1
    Advanced Member level 3
    Points: 3,695, Level: 14

    Join Date
    Feb 2016
    Posts
    714
    Helped
    1 / 1
    Points
    3,695
    Level
    14

    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 ?


    •   AltAdvertisement

        
       

  2. #2
    Advanced Member level 5
    Points: 24,850, Level: 38
    barry's Avatar
    Join Date
    Mar 2005
    Location
    California, USA
    Posts
    4,759
    Helped
    1055 / 1055
    Points
    24,850
    Level
    38

    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?



  3. #3
    Advanced Member level 5
    Points: 38,244, Level: 47
    Achievements:
    7 years registered

    Join Date
    Jun 2010
    Posts
    6,922
    Helped
    2036 / 2036
    Points
    38,244
    Level
    47

    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.



  4. #4
    Advanced Member level 3
    Points: 3,695, Level: 14

    Join Date
    Feb 2016
    Posts
    714
    Helped
    1 / 1
    Points
    3,695
    Level
    14

    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



    •   AltAdvertisement

        
       

  5. #5
    Advanced Member level 5
    Points: 24,850, Level: 38
    barry's Avatar
    Join Date
    Mar 2005
    Location
    California, USA
    Posts
    4,759
    Helped
    1055 / 1055
    Points
    24,850
    Level
    38

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

    Quote Originally Posted by TrickyDicky View Post
    @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!



  6. #6
    Super Moderator
    Points: 32,130, Level: 43
    ads-ee's Avatar
    Join Date
    Sep 2013
    Location
    USA
    Posts
    7,430
    Helped
    1742 / 1742
    Points
    32,130
    Level
    43

    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



    •   AltAdvertisement

        
       

  7. #7
    Advanced Member level 3
    Points: 3,695, Level: 14

    Join Date
    Feb 2016
    Posts
    714
    Helped
    1 / 1
    Points
    3,695
    Level
    14

    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 ?



  8. #8
    Super Moderator
    Points: 264,236, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    46,168
    Helped
    14041 / 14041
    Points
    264,236
    Level
    100

    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?



  9. #9
    Super Moderator
    Points: 32,130, Level: 43
    ads-ee's Avatar
    Join Date
    Sep 2013
    Location
    USA
    Posts
    7,430
    Helped
    1742 / 1742
    Points
    32,130
    Level
    43

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

    Quote Originally Posted by promach View Post
    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....

    Quote Originally Posted by promach View Post
    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.



  10. #10
    Advanced Member level 3
    Points: 3,695, Level: 14

    Join Date
    Feb 2016
    Posts
    714
    Helped
    1 / 1
    Points
    3,695
    Level
    14

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

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



  11. #11
    Advanced Member level 5
    Points: 38,244, Level: 47
    Achievements:
    7 years registered

    Join Date
    Jun 2010
    Posts
    6,922
    Helped
    2036 / 2036
    Points
    38,244
    Level
    47

    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



  12. #12
    Super Moderator
    Points: 264,236, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    46,168
    Helped
    14041 / 14041
    Points
    264,236
    Level
    100

    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

    Click image for larger version. 

Name:	rtl.PNG 
Views:	4 
Size:	17.5 KB 
ID:	155854

    Click image for larger version. 

Name:	gate level.PNG 
Views:	4 
Size:	50.0 KB 
ID:	155855


    1 members found this post helpful.

    •   AltAdvertisement

        
       

  13. #13
    Super Moderator
    Points: 32,130, Level: 43
    ads-ee's Avatar
    Join Date
    Sep 2013
    Location
    USA
    Posts
    7,430
    Helped
    1742 / 1742
    Points
    32,130
    Level
    43

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

    Quote Originally Posted by promach View Post
    @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.
    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];



  14. #14
    Advanced Member level 3
    Points: 3,695, Level: 14

    Join Date
    Feb 2016
    Posts
    714
    Helped
    1 / 1
    Points
    3,695
    Level
    14

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

    20 = 1

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

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



  15. #15
    Super Moderator
    Points: 32,130, Level: 43
    ads-ee's Avatar
    Join Date
    Sep 2013
    Location
    USA
    Posts
    7,430
    Helped
    1742 / 1742
    Points
    32,130
    Level
    43

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

    Quote Originally Posted by promach View Post
    20 = 1

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



--[[ ]]--