Skip to content

Latest commit

 

History

History
149 lines (108 loc) · 3.99 KB

bit_manipulation.md

File metadata and controls

149 lines (108 loc) · 3.99 KB
Raw

Bit Manipulation

Operator Use Case Explanation Example Status
AND a & b if a == b == 1, then a & b = 1, otherwise = 0 1 & 1 = 1, 1 & 0 = 0,0 & 1 = 0, 0 & 0 = 0 OK
OR a | b if a == 1 or b == 1, then a | b = 1, otherwise = 0 1 | 1 = 1, 1 | 0 = 1,0 | 1 = 1, 0 | 0 = 0 OK
XOR a ^ b if (a,b) = (1,0) or (0,1), then a ^ b = 1, otherwise = 0 1 ^ 1 = 0, 1 ^ 0 = 1,0 ^ 1 = 1, 0 ^ 0 = 0 OK
NOT - a inverse AGAIN
LEFT MOVE a << b left shift a ( in binary) b times 9 << 2 = 36 OK
RIGHT MOVE a >> b right shift a ( in binary) b times 9 >> 2 = 2, -9 >> 2 = -3 AGAIN
RIGHT MOVE AND ADD 0 a >>> b right shift a ( in binary) b times, remove out-of-boundry bit, and add 0 left 19 >>> 2 = 4 AGAIN

Property

  • XOR

    • Taking XOR of a number with itself returns 0, e.g.,

      • 1 ^ 1 = 0
      • 29 ^ 29 = 0

    • Taking XOR of a number with 0 returns the same number, e.g.,

      • 1 ^ 0 = 1
      • 31 ^ 0 = 31

    • XOR is Associative & Commutative, which means:

      • (a ^ b) ^ c = a ^ (b ^ c)
      • a ^ b = b ^ a

Example 1

  • 15 & 9 = 9 (1111 & 1001 = 1001) (bin(15) = 1111, bin(9) = 1001)
  • 15 | 9 = 15 (1111 | 1001 = 1111) (bin(15) = 1111, bin(9) = 1001)
  • 15 ^ 9 = 6 (1111 ^ 1001 = 0110) (bin(15) = 1111, bin(9) = 1001)
  • 9 << 2 = 36 ( bin(9) = 1001, left shift 2 times -> 100100 -> int('100100', 2) = 36)
  • 9 >> 2 = 2 ( bin(9) = 1001, right shift 2 times -> 10 -> int('10', 2) = 2)
  • -9 >> 2 = -3
  • 19 >>> 2 = 4 ( bin(19) = 10001, right shift 2 times -> 100 -> add 0 make the length same as origin -> 00100 -> bin('100',2 )= 4)
  • Minus : 0 -> 1, 0 -> 1 then add 1
  • - (9) : - (1001) -> (0110) + 1 -> 0111
  • - (38) : - (00100110) -> (11011001) + 1 -> 11011010

Example 2

# binary 1 = 01 
# binary 2 = 10
# so -> 01 XOR 10 = 11 -> 3 
1 ^ 2 = 3 

# binary 1 = 01 
# binary 3 = 11
# so -> 01 XOR 11 = 10 -> 2
1 ^ 3 = 2 

# binary 1 =  01 
# binary 4 = 100
# so -> 01 XOR 100 =  101 -> 5 
1 ^ 4 = 5

Example 3

  • Calculate XOR from 1 to n ?
Input : n = 6
Output : 7
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6  = 7

Input : n = 7
Output : 0
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0

# Python 3 Program to find 
# XOR of numbers from 1 to n. 

# Function to calculate xor 
def computeXOR(n) : 

    # Modulus operator are expensive 
    # on most of the computers. n & 3 
    # will be equivalent to n % 4. 

    # if n is multiple of 4 
    if n % 4 == 0 : 
        return n 

    # If n % 4 gives remainder 1 
    if n % 4 == 1 : 
        return 1

    # If n%4 gives remainder 2 
    if n % 4 == 2 : 
        return n + 1

    # If n%4 gives remainder 3 
    return 0

# Driver Code 
if __name__ == "__main__" : 

    n = 5

    # function calling 
    print(computeXOR(n)) 
        
# This code is contributed by ANKITRAI1

Example 4

  • Given an array of n-1n−1 integers in the range from 11 to nn, find the one number that is missing from the array ?
def find_missing_number(arr):
    n = len(arr) + 1
    # x1 represents XOR of all values from 1 to n
    x1 = 1
    for i in range(2, n+1):
        x1 = x1 ^ i

    # x2 represents XOR of all values in arr
    x2 = arr[0]
    for i in range(1, n-1):
        x2 = x2 ^ arr[i]
  
    # missing number is the xor of x1 and x2
    return x1 ^ x2

def main():
    arr = [1, 5, 2, 6, 4] 
    print('Missing number is:' + str(find_missing_number(arr)))

main()

Ref