🧩 Algorithm

Write an efficient program to count number of 1s in binary representation of an integer.

Source

🧩 Code

def counting_1bits(value)
  count = 0

  while value > 0
    count += value & 1
    value >>= 1
  end

  count
end

🧩 Example

Input

As an input, I have an integer. Let’s say 5.

The binary representation of 5 is 101.

Output

What I need to know is how many 1s there are in the binary representation of 5 (101) which is 2.

Explanation

This algorithm can be solved if we know how to use Ruby’s Bitwise Operators. Particularly & and >> in this case. This article is really great to understand them.

Taking the example of the binary representation of 5:101

I can use the bitwise operator & to compare each bit of the given integer with 1.

The bitwise AND operator compares the binary representation of two integers bit by bit; if the same bits in both integers are set to 1 the resulting integer’s binary representation will have the corresponding bit set to 1. If not, the bit will be set to 0.

n = 5
n & 1
=> 1

n.to_s(2)
=> "101"

Why ? We are comparing here the binary representation of 5 to the binary representation of 1, in other words we can comparing 101 to 1, and more particularly the same bits so 1 and 1, which results in 1.

Then I use the >> operator.

The bitwise left and right shift operators shift the bits of an integer’s binary representation to the left or right by the given number of positions, padding with zeros or truncating bits as necessary

n >>= 1
=> 2

n.to_s(2)
=> "10"

The binary representation of n becomes 10 (I cropped the 101).

So now, comparing 10 to 1 we get 0 (as 0 & 1 = 0)

n & 1
=> 0

Finishing.

The binary representation of n becomes 1 (I cropped the 10).

So now, comparing 1 to 1 we get 1 (as 1 & 1 = 1)

n >>= 1
=> 1

n & 1
=> 1

n.to_s(2)
=> "1"

So we have two 1 !

🧩 Source code

here :)

Updated: