Bitwise operations and hacks

Bitwise operators

bitwise and (&)
bitwise or (|)
bitwise xor (^)
bitwise not (~)
bitwise shift left (<<)
bitwise shift right (>>)

Assuming that you know what the basic bitwise operators do, we’ll move directly to the uses and tricks and I will make an effort to explain the logic behind the tricks so you understand the basic rather than trying to remember the solution.

Real time execution

1. Check if the integer is odd or even
To check for the odd or even integer, we just have to look at the last bit in the number and determine if it’s odd or even. If you do a bitwise and (&) of a number, you are essentially setting all the bits except the least significant bit to 0. The least significant bit will be set to 1 if the original number has it set to 1 and similarly 0 if the original number has it set to 0. Therefore, doing a bitwise and with 1 would always result in a 0 or 1, with 0 denoting an even number and 1 denoting a positive number. This approach works for both positive and negative integers represented in binary because the most significant with AND’ed with 0 becomes 0 and we are essentially making a judgement based on the least significant bit.

Checking if 40 is odd/even returns 0

    101000
&   000001
    ------
    000000
    ------

Checking if 111 is odd/even returns 1

    1101111
&   0000000
    -------
    0000001
    -------

Python method to check if number is even or odd

def bitwise_EvenOdd(num):
  '''
  Return 1 if Odd and 0 if Even
  '''
  return num & 1
x = 5
print('Odd(1)/Even(0) test for {}: {}'.format(x, bitwise_EvenOdd(x)))
x = 6
print('Odd(1)/Even(0) test for {}: {}'.format(x, bitwise_EvenOdd(x)))
x = 133
x = -133
print('Odd(1)/Even(0) test for {}: {}'.format(x, bitwise_EvenOdd(x)))
x = -2048
print('Odd(1)/Even(0) test for {}: {}'.format(x, bitwise_EvenOdd(x)))

2. Check if the nth bit is set
The concept is similar to doing a bitwise AND with 1 to determine if the number is even or odd. This time around, we need to check on the nth bit in a number rather than the most significant bit. Therefore, we need to perform an AND operation with a number that has 1 set in it’s nth bit. How do we generate that number with 1 in it’s nth bit? The answer is using a bitwise SHIFT LEFT operation on 1. This would move the bit 1 n times to it’s left and getting us the number that we desire.

Here is what happens if you shift 1 several positions to the left:

1         00000001    (same as 1<<0)
1<<1      00000010
1<<2      00000100
1<<3      00001000
1<<4      00010000
1<<5      00100000
1<<6      01000000
1<<7      10000000

Now if you did an AND operation on the number with this left shifted 1, you will get a 0 if the nth bit in the original number was 0. If the nth bit in the original number was 1, then you will get a non-zero result. Applies for negative numbers as well, because AND’ing with a left shifted 1 will result in making the MSB zero anyways.

Here’s a python method to check if the nth bit is set in the integer or not. Note that the nth index for the LSB (Least Significant Bit) starts from 0 in this case and not 1.

def bitwise_checkNthBit(num, n):
  '''
  Check if n th bit is set in the number num or not
  '''
  n_shifted_one = 1<<n
  print(n_shifted_one)
  return num & n_shifted_one

num, n = 10, 3
result = bitwise_checkNthBit(num, n)
print('Checking if LSB at position {} is set in {}: {}'.format(n, num, result))
num, n = 10, 2
result = bitwise_checkNthBit(num, n)
print('Checking if LSB at position {} is set in {}: {}'.format(n, num, result))

3. Set the nth bit
Just how we did an AND operation on the number with the left shifted 1 to determine if the nth bit is set or not, we can use a similar concept to set the nth. This time around, the objective is to set the nth bit. If we OR’ed that bit with 1, it would result in setting the bit to 1 – irrespective of the original value. So in the above method if we just changed the AND operation with the OR operation, we would set the nth bit in the number.

e.g. 10 is represented as 1010 in Binary. If we set the 2nd bit (remember, index starting from 0 from the LSB) the number would be come 1110 which is 14 in Decimal.

def bitwise_setNthBit(num, n):
  '''
  Check if n th bit is set in the number num or not
  '''
  n_shifted_one = 1<<n
  return num | n_shifted_one

num, n = 10, 2
result = bitwise_setNthBit(num, n)
print('Setting LSB at position {} on {} results in {}'.format(n, num, result))
num, n = -18, 2
result = bitwise_setNthBit(num, n)
print('Setting LSB at position {} on {} results in {}'.format(n, num, result))
print('')

Please note that any operations performed on negative binary numbers are done on 2’s compliment of the number. e.g. to work with -18, convert 18 into 2’s complement and then perform the operation. Then convert the 2’s compliment number into decimal to get the decimal representation of the negative number.

4. Unset the nth bit
To unset the nth bit, we need to make it 0. That’s easy right, just AND the bit by 0. Now the question is how do we get 0 in a specific bit? There isn’t a direct way. We need to get 1 in the specific by by doing the left shift, and then complement the number to get 0 in the specific position and convert the others to 0.

def bitwise_unsetNthBit(num, n):
  '''
  Check if n th bit is set in the number num or not
  '''
  n_shifted_one = 1<<n
  return num & ~n_shifted_one

num, n = 21, 2
result = bitwise_unsetNthBit(num, n)
print('Unsetting LSB at position {} on {} results in {}'.format(n, num, result))
num, n = -18, 3
result = bitwise_unsetNthBit(num, n)
print('Unsetting LSB at position {} on {} results in {}'.format(n, num, result))
print('')

Again, when working with negative numbers, you need to convert the decimal to the 2’s complement and then operate on that number.

5. Toggle the nth bit
We need to convert 0 to 1 and vice-versa. This should be fairly simple, need to do a XOR with 1. 0^1 will become 1 and 1^1 will become 0. The other bits in the number should be XOR’ed with 0 because 0^0 stays 0 and 1^1 stays 1 – so there is no change when a bit is XOR’ed with 0.

def bitwise_toggleNthBit(num, n):
  '''
  Toggle n th bit in the number num
  '''
  n_shifted_one = 1<<n
  return num ^ n_shifted_one

num, n = 42, 1
result = bitwise_toggleNthBit(num, n)
print('Toggling LSB at position {} on {} results in {}'.format(n, num, result))
num, n = 42, 2
result = bitwise_toggleNthBit(num, n)
print('Toggline LSB at position {} on {} results in {}'.format(n, num, result))
num, n = -18, 1
result = bitwise_toggleNthBit(num, n)
print('Toggling LSB at position {} on {} results in {}'.format(n, num, result))
print('')

6. Find the non-duplicate number in a list
If given a list that has duplicates except one number, bitwise XOR is a useful way of getting the standalone number.
e.g.
In the list of [3,4,2,3,1,6,1,2,4] => 6 is the standalone number.
In the list of [13,4,289,13,11,611,11,289,4] => 611 is the standalone number.

How do we get to this answer? Let’s look at the following logic logic:

  1. Any number when XOR’ed by itself returns 0, i.e. x ^ x = 0. That’s because all the bits will XOR with their corresponding equal bits and the eventual result will be 0
  2. Any number when XOR’ed with 0 returns the number itself, i.e. x ^ 0 = x. That’s because if x has a bit 1, then 1^0 is 1 and if x has a bit 0, then 0^0 is 0. Thus generating the number itself.

We could use the above logic to compute the standalone non-duplicate number in a list in which all other numbers occur two times. The XOR or number by itself will return 0 as in (1) and thus all the duplicates will cancel themselves out. And finally, we will have the number remaining and XOR of the number with 0 returns the number itself.

Here’s the code to compute the duplicate from the list:

def nonDupInt(nums):
  xor = 0
  for i in nums:
    xor ^= i
  return xor

nums = [3,4,2,3,1,6,1,2,4]
result = nonDupInt(nums)
print('Non duplicate number in {} is {}'.format(nums, result))

nums = [13,4,289,13,11,611,11,289,4]
result = nonDupInt(nums)
print('Non duplicate number in {} is {}'.format(nums, result))

7. Find the missing number in a series
Because we know that nums contains n numbers and that it is missing exactly one number on the range [0..n−1], we know that n definitely replaces the missing number in nums. Therefore, if we initialize an integer to n and XOR it with every index and value, we will be left with the missing number.

Here’s the code to find the missing number in the series:

def missingNumber(nums):
  xor = len(nums)
  for i, n in enumerate(nums):
    xor ^= i ^ n
  return xor

nums = [3,0,1]
result = missingNumber(nums)
print(f'Number {result} is missing in series {nums} | {result==2}\n')

nums = [9,6,4,2,3,5,7,0,1]
result = missingNumber(nums)
print(f'Number {result} is missing in series {nums} | {result==8}\n')

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.