How can I get the position of bits

Question

I have a decimal number which I need to convert to binary and then find the position of one's in that binary representation.

Input is 5 whose binary is 101 and Output should be

1
3

Below is my code which only provides output as 2 instead I want to provide the position of one's in binary representation. How can I also get position of set bits starting from 1?

public static void main(String args[]) throws Exception {
    System.out.println(countBits(5));
}

private static int countBits(int number) {
    boolean flag = false;

    if (number < 0) {
        flag = true;
        number = ~number;
    }
    int result = 0;
    while (number != 0) {
        result += number & 1;
        number = number >> 1;
    }
    return flag ? (32 - result) : result;
}

Solution 1

Your idea of having countBits return the result, instead of putting a System.out.println inside the method, is generally the best approach. If you want it to return a list of bit positions, the analogue would be to have your method return an array or some kind of List, like:

private static List<Integer> bitPositions(int number) {

As I mentioned in my comments, you will make life a lot easier for yourself if you use >>> and get rid of the special code to check for negatives. Doing this, and adapting the code you already have, gives you something like

private static List<Integer> bitPositions(int number) {
    List<Integer> positions = new ArrayList<>();
    int position = 1;
    while (number != 0) {
        if (number & 1 != 0) {
            positions.add(position);
        }
        position++;
        number = number >>> 1;
    }
    return positions;
}

Now the caller can do what it wants to print the positions out. If you use System.out.println on it, the output will be [1, 3]. If you want each output on a separate line:

for (Integer position : bitPositions(5)) {
     System.out.println(position);
}

In any case, the decision about how to print the positions (or whatever else you want to do with them) is kept separate from the logic that computes the positions, because the method returns the whole list and doesn't have its own println.

(By the way, as Alex said, it's most common to think of the lower-order bit as "bit 0" instead of "bit 1", although I've seen hardware manuals that call the low-order bit "bit 31" and the high-order bit "bit 0". The advantage of calling it "bit 0" is that a 1 bit in position N represents the value 2^N, making things simple. My code example calls it "bit 1" as you requested in your question; but if you want to change it to 0, just change the initial value of position.)

Solution 2

Binary representation: Your number, like anything on a modern day (non-quantum) computer, is already a binary representation in memory, as a sequence of bits of a given size.

Bit operations You can use bit shifting, bit masking, 'AND', 'OR', 'NOT' and 'XOR' bitwise operations to manipulate them and get information about them on the level of individual bits.

Your example

For your example number of 5 (101) you mentioned that your expected output would be 1, 3. This is a bit odd, because generally speaking one would start counting at 0, e.g. for 5 as a byte (8 bit number):

     76543210  <-- bit index
5    00000101

So I would expect the output to be 0 and 2 because the bits at those bit indexes are set (1).

Your sample implementation shows the code for the function

private static int countBits(int number)

Its name and signature imply the following behavior for any implementation:

• It takes an integer value number and returns a single output value.
• It is intended to count how many bits are set in the input number.

I.e. it does not match at all with what you described as your intended functionality.

A solution

You can solve your problem using a combination of a 'bit shift' (>>) and an AND (&) operation.

int index = 0; // start at bit index 0

while (inputNumber != 0) { // If the number is 0, no bits are set

    // check if the bit at the current index 0 is set
    if ((inputNumber & 1) == 1)         
        System.out.println(index);  // it is, print its bit index.

    // advance to the next bit position to check
    inputNumber = inputNumber >> 1; // shift all bits one position to the right
    index = index + 1;              // so we are now looking at the next index.
}

If we were to run this for your example input number '5', we would see the following:

iteration   input  76543210     index    result
1           5      00000101     0        1 => bit set.
2           2      00000010     1        0 => bit not set.
3           1      00000001     2        1 => bit set.
4           0      00000000     3        Stop, because inputNumber is 0    

Solution 3

You'll need to keep track of what position you're on, and when number & 1 results in 1, print out that position. It look something like:

...
int position = 1;
while (number != 0) {
    if((number & 1)==1)
        System.out.println(position);
    result += number & 1;
    position += 1;
    number = number >> 1;
}
...

Solution 4

There is a way around working with bit-wise operations to solve your problem.
Integer.toBinaryString(int number) converts an integer to a String composed of zeros and ones. This is handy in your case because you could instead have:

public static void main(String args[]) throws Exception {
    countBits(5);
}

public static void countBits(int x) {
  String binaryStr = Integer.toBinaryString(x);
  int length = binaryStr.length();
  for(int i=0; i<length; i++) {
    if(binaryStr.charAt(i)=='1')
      System.out.println(length-1);
  }
}

It bypasses what you might be trying to do (learn bitwise operations in Java), but makes the code look cleaner in my opinion.

View more solutions