5 months

# Bit Manipulation

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.

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)

## Bitwise Operators

Working with primitive data types like bytesbooleansintsfloatsdoubles, 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

AND Operator (`&`) gives 1 only if both of the operands are 1, otherwise 0.

## Check if the integer is even or odd: def check_even_or_odd(n: int) -> str:                                      if (n & 1) == 0:                                                                             return f"{n} is even number."                                            else:                                                                                             return f"{n} is odd number."

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:

• Bitwise AND  in order to extract a subset of the bits in the value
• ``````    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    output``````
• Bitwise OR in order to set a subset of the bits in the value
• ``````data    10110010
________
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    output``````
``mask = ~(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.

# Toggle all bits after most significant bit

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)

# Count set bits in an integer

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.`               ``     `

# Count unset bits of a number

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)

# Equal Sum and XOR

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)                                                       `

See all(3)

Tags

Topics