I’m writing this post to share my thoughts on how to count the number of set bits in an integer using 4 different methods. I encountered this problem online and then decided to try my best to find all the possible solutions that I can think of.

1. For loop to add up every bit

So, the basic idea is to have a for loop, and just loop all the bits and add them up. This will give you the answer. The code is in the following:

module count;

  int A;

  int result;

  initial begin

    A = 7;

    result = 0;

    for(int i =0; i < 32; i++) begin

      result +=A[i];

    end

    $display("result is %d", result);

  end

endmodule

 

This can be done by Verilog Syntax. For SystemVerilog users, we can implement using foreach loop which doesn’t require us to know how many bits the number has.

module count;



  int A;



  int result;



  initial begin



    A = 7;



    result = 0;



    foreach(A[i])



      result +=A[i];



    $display("result is %d", result);



  end



endmodule

 

2. Loop through the number and use bit comparison at the last bit

So, the basic the idea is to only add 1 to the result when the last bit is 1, which can be accomplished by using a mask of number 1. After each iteration, the number is shifted 1 bit to the right. We are using while loop here, and the condition is valid only when the number is still positive, which means until its highest bit. This can potentially save time.

module count;

  int A;

  int result;

  initial begin

    A = 7;
    result = 0;

    while(A)begin

      result += A&1;

      A>>=1;

    end

    $display("result is %d", result);

end

endmodule

 

3. Brian Kernighan’s Algorithm

It’s somewhat about bit manipulation too. The idea is to subtract 1 from the original number, and this toggles to the rightmost set bit. If we subtract 1 from the original number and do bitwise with itself, we will unset the rightmost set bit. If we do a loop, we can unset all the set bits, and count the number of the set bits as well.

 

module count;

  int A;

  int result;

  initial begin

    A = 7;

    result = 0;

    while(A)begin

      A = A&(A-1);

      result++;

    end

    $display("result is %d", result);

  end

endmodule

 

4. SystemVerilog builtin function $countones

SystemVerilog has $countones to count number of ones in a bit vector. The more general form of this function is $countbits, which you can used to count 0, 1, x, or z in a bit vector. You can refer to LRM 20.9 for more information.

Those are all I want to share today. Leave me a comment if you have any questions or if you find other ways to solve this problem. 🙂

P.S. These two code snippets plugins suck. I really need to find a better one.