Bit Manipulation 4% of LeetCode Problems

Knowledge

Two’s complement and negative number: The binary representation of -k as a N-bit number is concat(1, 2^(N-1)-k) ==representation in positive, flip each bit, and +1.

Arithmetic right shift: shift to the right side, but fill in the new bits with the value of the sign bit, the same result as divide 2^N, for shifting N bits

Logical right shift, we shift values and put a 0 in the most significant bit. It is indicated with a >>> operator.

Get Bit: (num&(1<<i))!=0.

Set Bit: (num|(1<<i))

Clear Bit: First create a 1110111 by creating the reverse of 0001000 and negating it. Then perform AND with num, then we will clear the ith bit and leave the remainder unchanged. mask = ~(1<<i), num&mask.

To clear all bits from the most significant bit till i, we create a mask with a 1, 1<<i. Then we subtract 1 from it, i=4, 00010000->00001111, we left 4 bits untouched. mask = (1<<i)-1, num&mask

To clear all bits from i through 0. mask = (-1<<(i+1)) ,-1 is all 1s, then we have a sequence of 1s followed by i 0 bits. num & mask

Update Bits: mask = ~(1<<i), use this to clear at first, (num&mask) | (value<<i)

XOR: Bitwise XOR ( ^ ) like the other operators (except ~) also take two equal-length bit patterns. If both bits in the compared position of the bit patterns are 0 or 1, the bit in the resulting bit pattern is 0, otherwise 1. (to detect difference)

A = 5 = 0101, B = 3 = 0011
A ^ B = 0101 ^ 0011 = 0110 = 6

Return the rightmost 1 in the binary representation of a number.

Example: For 1010, you should perform some operations to give 0010 as the output. For 1100, you should give 0100. Similarly for 0001, you should return 0001.

Try finding the solution yourself. The biggest hint you have is you can do it using ( ^ ) operator. After you’re done, scroll down.

Solution:

For this problem, you need to know a property of binary subtraction. Check if you can find out the property in the examples below,

1000–0001 = 0111

0100–0001 = 0011

1100–0001 = 1011

The property is, the difference between a binary number n and n-1 is all the bits on the right of the rightmost 1 are flipped including the rightmost 1. Using this amazing property, we can get our solution as

x ^ (x & (x -1))

For a given array of repeated elements, exactly one element is not repeated. You need to return the non-repeated element.

[1, 2, 5, 4, 6, 8, 9, 2, 1, 4, 5, 8, 9]

You can refer the example above. You will need to return 6.

There exists a solution of linear complexity.

Solution:

This one is kinda straightforward. You’ll need to know the following properties

n ^ n = 0

n ^ 0 = n

Algorithm:

1. Create a variable v with value 0.
2. Iterate over array from i = 0 to i = n-1
3. Perform v ^ arr[i] and store the result in v for every iteration.
4. Return v.

So, for my final question, i would like to give you a problem that is quite challenging. This one do not require the use of any new property of XOR other than the ones mentioned above.

Write a function to determine the number of bits required to convert integer A to integer B.

Solution:

a XOR b = c => c XOR b= a, eg. a=00111011, b=10100000 , c= 10011011, c ^b= a

Examples

190. Reverse Bits

def reverseBits(self, n):
        ans=0
        for i in range(32)[::-1]: #from low to high
            ans=ans
            mask=1<<i
            set_mask=1<<(31-i)
            if (mask&n)!=0: #get bit
                #set bit to 1
                ans|=set_mask
        return ans

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        v=0
        for e in nums:
            v=v^e
        return v

Single Number II - LeetCode

http://www.cnblogs.com/daijinqiao/p/3352893.html

389. Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.

Solution: Using bit manipulation and with O(1) we can find it in O(M+N) time, which is the best BCR:

def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        v=0
        for c in s:
            v=v^ord(c)
        for c in t:
            v=v^ord(c)
        return chr(v)

421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231. Find the maximum result of ai XOR aj, where 0 ≤ i, j < n. Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.

Explanation: suppose a^b = max, then a^max = b, so we just need to prob the possible max, and check if the value we need to get the possible max is in the list. We can get the max with the previous answer^ 1 = possible max (keep the result from other digit, just to check the lowest digit, or answer+1). We visit the highest position to the lowest, start with the possible answer= 0, so that the possible max is answer+1 =1, when we go to the next position, answer =0, possible max is 1, the following process is showed as follows:

answer^ 1 is the possible max,

def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        answer = 0
        for i in range(32)[::-1]:
            answer <<= 1 # multiple it by two
            prefixes = {num >> i for num in nums} # shift right for n, divide/2^i, get the ith bit
            answer += any((answer^1) ^ p in prefixes for p in prefixes)# or answer+1
        return answer

201. Bitwise AND of Numbers Range

First let’s think what does bitwise AND do to two numbers, for example ( 0b means base 2)

4 & 7 = 0b100 & 0b111 = 0b100
5 & 7 = 0b101 & 0b111 = 0b101
5 & 6 = 0b101 & 0b110 = 0b100

The operator & is keeping those bits which is set in both number.

For several numbers, the operator & is keeping those bits which is 1 in every number.

In other word, a bit is 0 in any number will result in 0 in the answer’s corresponding bit.

Solution: The first solution is a O(n), it almost passed all the test, however, still with LTE

def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        ans = 0
        for i in range(32)[::-1]: #start from the most significant position
            ans=ans<<1
            mask = 1<<i
for e in range(m,n+1):
                if e&mask==0:
                    bZero=True
                    break
            if not bZero:
                ans=ans+1
        return ans

Now consider a range

[m = 0bxyz0acd, n=0bxyz1rst]

here xyzpacdrst all are digits in base 2.

We can find two numbers that are special in the range [m, n]

(1) m' = 0bxyz0111
(2) n' = 0bxyz1000

The bitwise AND of all the numbers in range [m, n] is just the bitwise AND of the two special number

rangeBitwiseAnd(m, n) = m' & n' = 0bxyz0000

This tells us, the bitwise and of the range is keeping the common bits of m and n from left to right until the first bit that they are different, padding zeros for the rest.

def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        i = 0
        while m != n:
            m >>= 1
            n >>= 1 #find the common bits, i counts how many zeros we need
            i += 1
        return n << i # common bits then we shift i left

Python

bit manipulation

algorithms