Computers represent all data internally as sequences of bits. Each bit can assume the value 0 or the value 1. The bitwise operators are used to manipulate the bits of integral operands both signed and unsigned. Unsigned integers are normally used with the bitwise operators. Bitwise manipulations are machine-dependent.
A binary number system is one of the four types of number systems, and it is used to define a number in a binary system. A binary number system represents a number in terms of only two digits, i.e., 0 (zero) and 1 (one).
Computers use a method called Two’s Complement to represent negative numbers. Also, this method can be more effective when performing mathematical operations like adding and subtracting.
In this method, the bit at the far left side of the bit pattern is the most significant bit, or MSB is used to indicate positive or negative numbers.
Positive numbers always start with a 0 and the remaining bits are used to store the actual size of the number.
Negative numbers always start with a 1 and the remaining bits are used to store the actual size of the number. The biggest negative number is the largest binary value. (e.g. 1111 is -1)
Working with primitive data types like bytes, booleans, ints, floats, doubles, or with data structures is normal for a programmer. Sometimes in Computer Science, you need to go beyond this to a deeper level where you need to understand the importance of bits.
This is especially important if you are working on data compression and encryption algorithms, optimization, data correction, error detection algorithms, and so on.
AND Operator (&) gives 1 only if both of the operands are 1, otherwise 0.
An integer is odd if and only if the least significant bit (LSB) is 1. By using AND (&) operator between given number (n) and 1, we are eliminating all bits other than LSB. After this operation, if the result is 0, that means LSB is 0 and the number is even. Otherwise, it is odd.
0001 0001 (Binary of 17)
0000 0001 (Binary of 1)
& ------------------------------------
0000 0001 ------> 1, so 17 is odd number
0000 1000 (Binary of 8)
0000 0001 (Binary of 1)
& ------------------------------------
0000 0000 ------> 0, so 8 is even number
OR Operator
OR Operator (|) gives 0 only if both of the operands are 0, otherwise 1.
a = 10 = 1010 (Binary)
b = 4 = 0100 (Binary)
a | b = 1010
|
0100
= 1110
= 14 (Decimal)
XOR Operator
XOR Operator (^) gives 1 for odd numbers of 1s, otherwise 0.
12 = 00001100 (In Binary)
25 = 00011001 (In Binary)
Bitwise XOR Operation of 12 and 25
00001100
^ 00011001
________
00010101 = 21 (In decimal)
One’s Complement Operator
One’s Complement Operator (~) is a unary operator and converts 0s to 1s and 1s to 0s.
a = 10 = 1010 (Binary)
~a = ~1010
= -(1010 + 1)
= -(1011)
= -11 (Decimal)
Left Shift Operator
Left Shift Operator (<<) shifts the bits to the left and insert 0 bit at least a significant bit.
b = -10 = 1111 0110 (Binary)
b << 1 = 1110 1100 = -20
b << 2 = 1101 1000 = -40
Right Shift Operator
Right Shift Operator (>>) shifts the bits to the right and the operator inserts 0 bit at the most significant bit.
a = 10 = 0000 1010 (Binary)
a >> 1 = 0000 0101 = 5
What is Bit Mask?
Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a byte. A bit mask (or Bitmap) is a data structure, usually an integer or array of bits, that represents a bit pattern that signifies a particular state in a particular computational problem. It takes advantage of bitwise operations.
We mostly use the following notations/operations on masks:
bit(i, mask) – the i-th bit of mask
count(mask) – the number of non-zero bits in the mask
first(mask) – the number of the lowest non-zero bit in the mask
set(i, mask) – set the ith bit in the mask
check(i, mask) – check the ith bit in the mask
We use bit masks because:
- it is memory efficient in most problems
- it is computationally efficient as we can use bitwise operations which are natively supported by the computer system and will be faster than other operations like addition (+).
Masking is the act of applying a mask to a value. This is accomplished by doing:
1 1 1 0 1 1 0 1 input
(&) 0 0 1 1 1 1 0 0 mask
------------------------------
0 0 1 0 1 1 0 0 outputdata 10110010
mask | 01000000
________
ans = 11110010 1 1 1 0 1 1 0 1 input
(^) 0 0 1 1 1 1 0 0 mask
------------------------------
1 1 0 1 0 0 0 1 outputmask = ~(1<<2) [Bitwise complement(~) operator : it will flip all bits ~(11110000) = (00001111)]Bit operators are a useful way to pass a set of named boolean arguments to a function.
Masks are used with IP addresses in IP ACLs (Access Control Lists) to specify what should be permitted and denied.
In computer graphics, when a given image is intended to be placed over a background, the transparent areas can be specified through a binary mask.
We can toggle a bit by doing XOR of it with 1 (Note that 1 ^ 0 = 1 and 1 ^ 1 = 0). The idea is to take a number temp with only one bit set. One by one move the only set bit of temp to left and do XOR of it with n until it crosses MSB (Most Significant Bit) of n.
# Python program to toggle set bits starting from MSB
def toggle(n):
# temporary variable to use XOR with one of a n
temp = 1
# Run loop until the only set bit in temp crosses MST of n.
while (temp <= n):
# Toggle bit of n corresponding to current set bit in temp.
n = n ^ temp
# Move set bit to next higher position.
temp = temp << 1
return n
Time Complexity: O(log n) Auxiliary Space: O(1)
Another Approach:
from math import log
# Returns a number which has all set bits starting from MSB of n
def toggle(num):
# the number of bits is equal to log2num + 1
n = int(log(num, 2)) + 1
# calculating mask
mask = pow(2, n) - 1
# toggling bits using xor with mask
return num ^ mask
Time Complexity: O(logn) Auxiliary Space: O(1)
Optimization:
def setAllBitsAfterMSB(n):
# This makes sure two bits (From MSB and including MSB) are set
n |= n>>1
# This makes sure 4 bits (From MSB and including MSB) are set
n |= n>>2
n |= n>>4
n |= n>>8
n |= n>>16
return n
def toggle(n):
n = n ^ setAllBitsAfterMSB(n)
return n
Time Complexity: O(1) Auxiliary Space: O(1)
Write an efficient program to count the number of 1s in the binary representation of an integer.
Input : n = 7
Output : 3
Binary representation of 7 is 111 and has 3 set bits
Input : n = 17
Output : 2
Binary representation of 17 is 10001 and has 2 set bits.
# Python3 program to Count set bits in an integer
def countSetBits(n):
count = 0
while (n):
count += n & 1
n >>= 1
return count
Time Complexity: O(logn) Auxiliary Space: O(1)
Recursive Function:
def countSetBits( n):
if (n == 0):
return 0
else:
# if last bit set add 1 else add 0
return (n & 1) + countSetBits(n >> 1)
Time Complexity: O(log n) Auxiliary Space: O(1)
Brian Kernighan’s Algorithm:
Subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost set bit.
For Example :
8 in binary is 00001000
7 in binary is 00000111
So if we subtract a number by 1 and do it bitwise & with itself (n & (n-1)), we unset the rightmost set bit. If we do n & (n-1) in a loop and count the number of times the loop executes, we get the set bit count.
def countSetBits(n):
count = 0
while (n):
n &= (n-1)
count += 1
return count
n = 9 (1001)
count = 0
Since 9 > 0, subtract by 1 and do bitwise & with (9-1)
n = 9&8 (1001 & 1000)
n = 8
count = 1
Since 8 > 0, subtract by 1 and do bitwise & with (8-1)
n = 8&7 (1000 & 0111)
n = 0
count = 2
Since n = 0, return count which is 2 now.
Time Complexity: O(logn) Auxiliary Space: O(1)
Recursive Function:
def countSetBits(n):
if (n == 0):
return 0
else:
return 1 + countSetBits(n & (n - 1))
Time Complexity: O(logn) Auxiliary Space: O(1)
print(bin(4).count('1')) # output 1
print(bin(15).count('1')); # oupput 4
Using Lookup table: We can count bits in O(1) time using the lookup table.
BitsSetTable256 = [0] * 256
# Function to initialise the lookup table
def initialize():
# To initially generate the table algorithmically
BitsSetTable256[0] = 0
for i in range(256):
BitsSetTable256[i] = (i & 1) + BitsSetTable256[i // 2]
# Function to return the count of set bits in n
def countSetBits(n):
return (BitsSetTable256[n & 0xff] +
BitsSetTable256[(n >> 8) & 0xff] +
BitsSetTable256[(n >> 16) & 0xff] +
BitsSetTable256[n >> 24])
Time Complexity: O(1) Auxiliary Space: O(1)
0xFF is a hexadecimal constant which is 11111111 in binary. By using bitwise AND ( & ) with this constant, it leaves only the last 8 bits of the original.
Unset bits in a binary number is represented by 0. Whenever we calculate the binary number of an integer value then it is formed as the combination of 0’s and 1’s. So, the digit 0 is known as the unset bit in the terms of the computer.
Given a number n, count unset bits after MSB (Most Significant Bit).
Input : 17
Output : 3
Binary of 17 is 10001
so unset bit is 3
Input : 7
Output : 0
def countunsetbits(n):
count = 0
# x holds one set digit at a time starting from LSB to MSB of n.
x = 1
while(x < n + 1):
if ((x & n) == 0):
count += 1
x = x << 1
return count
Time complexity is log(n). Space Complexity: O(1)
Optimization:
import math
def countUnsetBits(n):
x = n
# Make all bits set MSB(including MSB).This makes sure two bits(From MSB and
# including MSB) are set
n |= n >> 1
# This makes sure 4 bits(From MSB and including MSB) are set
n |= n >> 2
n |= n >> 4
n |= n >> 8
n |= n >> 16
t = math.log(x ^ n, 2)
# Count set bits in toggled number
return math.floor(t)
Time Complexity: O(1) Auxiliary Space: O(1)
Given a positive integer n, find count of positive integers i such that 0 <= i <= n and n+i = n^i .
Input: n = 12
Output: 4
12^i = 12+i hold only for i = 0, 1, 2, 3
for i=0, 12+0 = 12^0 = 12
for i=1, 12+1 = 12^1 = 13
for i=2, 12+2 = 12^2 = 14
for i=3, 12+3 = 12^3 = 15
# Python3 program to print count of values such that n+i = n^i
# function to count number of values less than equal to n that satisfy the given condition
def countValues (n):
result = 0;
# Traverse all numbers from 0 to n and increment result only
# when given condition is satisfied.
for i in range(n + 1):
if ((n + i) == (n ^ i)):
result += 1;
return result;
Time Complexity: O(n) Space Complexity: O(1)
An efficient solution is as follows: we know that (n+i) = (n^i) + 2*(n&i). So n + i = n ^ i implies n & i = 0
# Function to count number of values less than equal to n that satisfy the given condition
def countValues(n):
# unset_bits keeps track of count of un-set bits in binary representation of n
unset_bits = 0
while(n):
if n & 1 == 0:
unset_bits += 1
n = n >> 1
# Return 2 ^ unset_bits
return 1 << unset_bits
Time Complexity: O(log(n)) Space Complexity: O(1)
Operator overloading, sometimes termed operator ad hoc polymorphism, is a specific case of polymorphism, where different operators have different implementations depending on their arguments. Operator overloading is generally defined by a programming language, a programmer, or both.
We can overload all existing operators but we can’t create a new operator. To perform operator overloading, Python provides some special function or magic function that is automatically invoked when it is associated with that particular operator. For example, when we use + operator, the magic method __add__ is automatically invoked in which the operation for + operator is defined.
When we use an operator on user defined data types then automatically a special function or magic function associated with that operator is invoked. Changing the behavior of operator is as simple as changing the behavior of method or function.
class D:
def __init__(self, x):
self.x = x
def __add__(self, y):
return self.x + y.x
ob1 = D(9)
ob2 = D(8)
ob3 = D("Python")
ob4 = D("Magic")
print(ob1 + ob2)
print(ob3 + ob4)
Output: 17
Python Magic
class Bitwise():
def __init__(self, value):
self.value = value
def __and__(self, obj):
print("And operator overloaded")
if isinstance(obj, Bitwise):
return self.value & obj.value
else:
raise ValueError("Must be a object of class Bitwise")
def __or__(self, obj):
print("Or operator overloaded")
if isinstance(obj, Bitwise):
return self.value | obj.value
else:
raise ValueError("Must be a object of class Bitwise")
def __xor__(self, obj):
print("Xor operator overloaded")
if isinstance(obj, Bitwise):
return self.value ^ obj.value
else:
raise ValueError("Must be a object of class Bitwise")
def __lshift__(self, obj):
print("lshift operator overloaded")
if isinstance(obj, Bitwise):
return self.value << obj.value
else:
raise ValueError("Must be a object of class Bitwise")
def __rshift__(self, obj):
print("rshift operator overloaded")
if isinstance(obj, Bitwise):
return self.value & obj.value
else:
raise ValueError("Must be a object of class Bitwise")
def __invert__(self):
print("Invert operator overloaded")
return ~self.value
if __name__ == "__main__":
a = Bitwise(17)
b = Bitwise(7)
print(a & b)
print(a | b)
print(a ^ b)
print(a << b)
print(a >> b)
print(~a)
