Bit Theory I

Every number is represented as a series of 1s and 0s.

BITWISE OPERATIONS

Logic Gate Tables

Hamming Weight is the total number of set bits or number of 1s in the binary representation of a number.

Brian Kernighan’s algorithm is used to find the total number of set bits in a number. If 1 is subtracted from a number, the bits are flipped(0 becomes 1 and 1 becomes 0) from the rightmost set bit or the least significant 1 in the binary representation. If the AND operation is done between a number, X and (X — 1) and updated to X, then the total number of set bits would be the number of times it takes to loop till X becomes 0. The AND operation is done to reduce the number.

Find the total number of set bits in a number or the Hamming Weight of a number.

To find the total number of set bits in a number, the algorithm is:

1. Initialize the counter to 0.
2. Till the number, X does not become 0, update X as (X & (X — 1)). Increment the counter, each time the loop executes.
3. Return the counter.

CODE:

class Solution:
    def hammingWeight(self, n: int) -> int:
        
        #Steps 1.
        c = 0
        
        #Steps 2.
        while n:
            n = n & (n - 1)
            c = c + 1
        
        #Steps 3.
        return c

PRACTICE:

Number of 1 Bits | Practice | GeeksforGeeks

Number of 1 Bits - LeetCode

Set Bits for coding interview round

Number of 1 Bits - InterviewBit

To check if the bits are the same are not, use the XOR operation. The XOR operation is checked bitwise. If the resultant’s i-th bit is 0 then the particular bit of the two numbers is the same else it is different. If the XOR operation is done on two numbers, then the total number of bits that are set to 1 are the total positions in which the bits differ. This is also the number of changes or flips that need to be done in any one of the numbers to make it the same as the other.

Find the total number of flips that need to be done on X to make it equal to Y.

To find the total number of flips that need to be done on a number, the algorithm is:

1. Take the XOR of two numbers to get the number of non-matching bits. Initialize the counter to 0.
2. Count the total number of set bits in the XORed number done in the previous steps.
3. Return the counter.

CODE:

class Solution:
 def findBits(self, x: int, y: int) -> int:
  
  #Steps 1.
  x = x ^ y
  ans = 0
  
  #Steps 2.
  while x:
   x = x & (x - 1)
   ans = ans + 1
  
  #Steps 3.
  return ans

PRACTICE:

Practice Problems | Techie Delight

Bit Difference | Practice | GeeksforGeeks

Number of Flips for coding interview round

Using the above logic, it is observed that the two numbers when equal and the XOR operation when performed will always result in 0 and the XOR of a number with 0 will always result in the number itself. So if given an even number of the same numbers, their XOR is always 0. This when XORed with another number, will always give the number itself.

Find the single number among the numbers where every element occurs twice except one.

1. Initialize the answer to 0.
2. Take the XOR of every element with the answer.
3. Return the answer.

CODE:

def uniqueElement(arr, n):
    
    #Steps 1.
    x = 0
    
    #Steps 2.
    for i in arr:
        x = x ^ i
    
    #Steps 3.
    return x

PRACTICE:

Single Element in a Sorted Array for coding interview round

Single Element in a Sorted Array - LeetCode

Find the element that appears once in sorted array | Practice | GeeksforGeeks

Single Number for coding interview round

NOTES:

Notes for Part 1