Bit

Count number of set bits in an Integer

Pinterest LinkedIn Tumblr

Write a program to count the set bits in byte arrays.

source Code

package com.dsacode.Algorithm.bit;
 
public class CountingSet {
     
    public CountingSet(){
        preCalculate();
    }
    public int countBits1(int num){
        int count=0;
        while(num > 0){
            num &= num-1;
            count++;
        }
        return count;
    }
     
    private int count[] = new int[256];
     
    void preCalculate(){
        for(int i=0; i < 256; i++){
            count[i] = countBits1(i);
        }
    }
     
    public int countBits2(int num){
        int total = 0;
        int mask = (1 << 8) - 1;
        for(int i=0 ; i < 4; i++){
            total += count[num & mask];
            num = num >>> 8;
        }
        return total;
    }
    public static void main(String args[]){
        CountingSet cb = new CountingSet();
        System.out.println("Count Bits '3636363' : "+cb.countBits1(3636363));
        System.out.println("Count Bits '3636363' using bit mupulation : "+cb.countBits2(3636363));
    }
 
}

Output

Number of Set Bits of '12': 2

Algorithm Explanation

Get the number.
Use Bits calculation to find the counting the set bits in byte arrays.

Reference

https://en.wikipedia.org/wiki/Bit_array

Write A Comment