Bit Manipulation

Tags: [bit_manipulation], [math], [two's_complement]

Two's complement

Link: [https://en.wikipedia.org/wiki/Two's_complement](https://en.wikipedia.org/wiki/Two's_complement)

Remember one sentence: "负数是先取反再加一", which means, if we have a positive integer x, so -x = (~x) + 1. For example, we have an integer 3, so -3 = (~3) + 1.

Sum two integers without using '+' and '-' operators

Link: https://leetcode.com/problems/sum-of-two-integers/#/solutions

class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        if not a:
            return b
        if not b:
            return a

        MAX_INT_32_BITS = 0x7FFFFFFF
        MASK_32_BITS = 0xFFFFFFFF

        while b:
            # a & b will find out all positions at where a and b both have '1', 
            # and these '1's will become carry.
            carry = (a & b) & MASK_32_BITS

            # a ^ b will find out all positions at where a and b have different bit, 
            # at these positions, either '1' belongs to a or '1' belongs to b,
            # then we assign all these bits to a
            a = (a ^ b) & MASK_32_BITS

            # we shift all bits in carrys to left by one position (make them bigger)
            # to be ready to add back to a in next round.
            b = (carry << 1) & MASK_32_BITS

            # each time we check b, if b become to 0, which means there is no carry, 
            # so we can stop.

        if a <= MAX_INT_32_BITS:
            return a
        else:
            # Because we mask a as a 32 bits int, and a has been greater than MAX_INT_32_BITS,
            # which means now a is a negative number, based on the "two's complement", 
            # the highest significant digits should be all '1's.
            # And we can image now a's 32th bit (from right to left) must be '1', because a now is a negative int.
            # But in Python there are more than 32 bits, so we also need to make all high significant bits to be '1'.
            # So first we use '~0' to get all '1's, then we shift it to left 32 times, making it has 32 '0's at right side,
            # something like '111111111111...1110000000...000', then we make it do 'OR' with a, 
            # to left all bits on the left side of a to be '1's, to build a real Python negative int.
            return (~0 << 32) | a

Revelation:

In Python, the integer is not 32 bits.
Two's complement: Always remember this sentence about two's complement "负数是先取反再加一", which means, if x is a positive int, -x = (~x) + 1. For example, we have 3, and -3 should be (~3) + 1.
One hex digit stands for 4 binary bits, such as 0xF (in hex) means 1111 (in binary).
Max int in 32-bits int is 0x7FFFFFFF.
Min int in 32-bits int is ~0x7FFFFFF.
32 bits mask is 0xFFFFFFFF.
num1 & num2, will get all the '1's at where num1 and num2 both has '1's, which can be used as the carry in the calculation.
num1 ^ num2, will get all the '1's at where num1 and num2 has different bits, either num1 at this position has '1' or num2 at this position has '1'. Think about why we do 'a = a ^ b', because we have store the carry, and if at the position a and b all have '1's, which will be '0' in the result, and carry will be '1', and carry will be shift to left by one position, then added to the next round calculation.

Note:

Time complexity = O(32) = O(1), because the worst case is each time there is some carry, and if the carry is not 0, we must keep doing the calculation (while loop), and there are at most 32 bits need to be calculated, so T = O(32) = O(1).

Subtract two integers without using '+' and '-' operators.

def get_subtract(a, b):
    if not b:
        return a

    MAX_INT_32_BITS = 0x7FFFFFF
    MASK_32_BITS = 0xFFFFFFFF

    while b:
        # Only a's bit is '0' and b's bit is '1', a's bit need to borrow from its higher bit,
        # so we use (~a) to revert all a's bits, make the a's '0' to '1' and '1' to '0', then & with b, 
        # which extracts all the bits at where a's bit was '0' and b's bit was '1'.
        # For example, a = '0101', and b = '0111', so (~a) = '1010', so (~a) & b = '0010', 
        # which is the bits we need borrow from the higher bits.
        borrow = ((~a) & b) & MASK_32_BITS

        # a ^ b will get all bits at where a's bit is different from b's bit,
        # which should be the bits of result at corresponding positions.
        # For example, a = '0101', b = '0111', a ^ b = '0010' which should be result of this round.
        a = (a ^ b) & MASK_32_BITS

        # shift the borrow to left one position, make it bigger, 
        # and the 'borrow' will be calculated in next round.
        b = (borrow << 1)

        # each round will check the b, which is the 'borrow', if the 'borrow' in this round is 0,
        # we can stop.

    if a <= MAX_INT_32_BITS:
        return a
    else:
        # Because we mask a as a 32 bits int, and a has been greater than MAX_INT_32_BITS,
        # which means now a is a negative number, based on the "two's complement", 
        # the highest significant digits should be all '1's.
        # And we can image now a's 32th bit (from right to left) must be '1', because a now is a negative int.
        # But in Python there are more than 32 bits, so we also need to make all high significant bits to be '1'.
        # So first we use '~0' to get all '1's, then we shift it to left 32 times, making it has 32 '0's at right side,
        # something like '111111111111...1110000000...000', then we make it do 'OR' with a, 
        # to left all bits on the left side of a to be '1's, to build a real Python negative int.
        return (~0 << 32) | a

if __name__ == '__main__':
    print 'Program is working'

    # a = 10
    # b = 1

    a = 10
    b = 100

    print get_subtract(a, b)

    print 'Program is end'

Note:

Time complexity = O(32) = O(1).

Bit Manipulation

Bit Manipulation

results matching ""

No results matching ""