191. Number of 1 Bits

Easy

Problem:

Accept an unsigned integer as input and output the number of 1 bits.

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

https://leetcode.com/problems/number-of-1-bits/

What to learn:

Variable swap using XOR

First, compute the XOR value of the different parts of two numbers using x^y. Then, doing x^y again yields the value of x. Next, assign this value to y, and when x^y is computed once more, since y is now set to x, the original value of y is returned. Now, assign this value to x, and the process is complete.

>>> x = 10
>>> y = 40
>>> (x^y)^x
40
>>> (x^y)^y
10

Variable swap using simple mathematics

This method is a good solution that doesn't require space complexity, as it doesn't need any additional space. However, there are limitations such as it must be a number.

>>> x = 9
>>> y = 4
>>> x += y
>>> x
13

>>> y = x - y
>>> y
4

>>> x -= y
>>> x
9

Solution:

Counting the number of ones

The result of this problem is the Hamming distance with bits all set to 0, which is referred to as the Hamming weight. In other words, we just need to compute the Hamming weight. So, we can simply count the number of 1s in the binary representation.

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')  

Bit operation

>>> bin(0b1000 & 0b111)
'0b0'
>>> bin(0b1010 & 0b1001)
'0b1000'
>>> bin(0b1011 & 0b1010)
'0b1010'

Each time we perform an AND operation with the value decremented by 1, a bit of 1 gets subtracted. If we repeat this operation until the value becomes 0, we can determine how many 1 bits are present in the entire bit sequence.

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count