1 month

Bit Tricks for Competitive Programming




Competitive Programming is a mental sport that enables you to code a given problem under provided constraints. The aim of competitive programming is to write source code of computer programs which are able to solve given problems. A vast majority of problems appearing in programming contests are mathematical or logical in nature. Typical such tasks belong to one of the following categories: combinatoricsnumber theorygraph theoryalgorithmic game theorycomputational geometrystring analysis and data structures. Problems related to constraint programming and artificial intelligence are also popular in certain competitions.

Competitive programming combines two topics: the design of algorithms and the implementation of algorithms. The design of algorithms consists of problem-solving and mathematical thinking. Skills for analyzing problems and solving them creatively are needed. An algorithm for solving a problem has to be both correct and efficient, and the core of the problem is often about inventing an efficient algorithm. Theoretical knowledge of algorithms is important to competitive programmers. Typically, a solution to a problem is a combination of well-known techniques and new insights. The techniques that appear in competitive programming also form the basis for the scientific research of algorithms. The implementation of algorithms requires good programming skills. In competitive programming, the solutions are graded by testing an implemented algorithm using a set of test cases. Thus, it is not enough that the idea of the algorithm is correct, but the implementation also has to be correct.

In competitive programming or in general, some problems seem difficult but can be solved very easily with little concepts of bit magic. 

Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Computer programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions. Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and bit shifts.

Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give many-fold speed-ups, as bit manipulations are processed in parallel, but the code can become more difficult to write and maintain.

1. Set a bit at n'th position in the number:                                                   

First, we left shift ‘1’ to n position via (1<<n). Then, use the ‘OR’ operator to set the bit at that position. ‘OR’ operator is used because it will set the bit even if the bit is unset previously in the binary representation of the number ‘num’.  If the bit would be already set then it would remain unchanged.

def set (num, pos):                                            

  # First step = Shift '1'   Second step = Bitwise OR

  num |= (1 << pos)                                

  return num                                                                                    

num, pos = 8, 1                                  

print(set(num, pos))                               output: 10

 

2. Set unset/clear a bit at n’th position:                                            

First, we left shift ‘1’ to n position via (1<<n) then we use bitwise NOT operator ‘~’ to unset this shifted ‘1’. Now after clearing this left shifted ‘1’ i.e making it to ‘0’ we will ‘AND'(&) with the number ‘num’ that will unset bit at nth position.

def unset(num, pos):                                             

    # Second Step: Bitwise AND this number with the given number

    num &= (~(1 << pos))                               

    return num                       

num, pos = 7, 1                                    

print(unset(num, pos))  output: 5                                                   

3.  Toggling a bit at nth position :                                 

 We will be using the ‘XOR’ operator here which is this ‘^’. The reason behind the ‘XOR’ operator is because of its properties. 

  • Properties of ‘XOR’ operator. 
    • 1^1 = 0                                                 
    • 0^0 = 0                         
    • 1^0 = 1                                       
    • 0^1 = 1                                                                          
  • If two bits are different then the ‘XOR’ operator returns a set bit(1) else it returns an unset bit(0).

def toggle(num, pos):                                            

  num ^= (1 << pos)                                  

  return num                                                           

num, pos = 4, 1                                                                

print(toggle(num, pos))       output: 6                                

XOR (^) operator in num ^ (1 << n) toggles the value from 0 to 1 or vice versa.

4. Checking if the bit at nth position is set or unset:                                                

We can use  ‘AND’ operator.  Left shift ‘1’ to the given position and then ‘AND'(‘&’).

def at_position(num,pos):                         

    bit = num & (<< pos)                    

    return bit                                                     

print( at_position(5, 0))  output: 1                                    

def set_nth_bit(num, n: int) -> str:                                         
    if num & (1 << n):                       
        return f"{num} (decimal) = {bin(num)} (binary) and {n}th bit is ALREADY set"
    else:                                                 
        set_nth_bit_result = num | (1 << n)
        return f"{n}th bit is set ({bin(num)} is changed to {bin(set_nth_bit_result)})"

Result of num | (1 << n) the operation sets the targeted bit. Because using OR (|)  operator on any value with 0 leaves the value the same but if we use OR (|) operator with 1, it changes the value to 1.

def unset_nth_bit(num, n: int) -> str:                      
    if num & (1 << n):                              
        unset_nth_bit_result = num & ~(1 << n)                                   
        return f"{n}th bit is unset ({bin(num)} is changed to {bin(unset_nth_bit_result)})"
    else:                                           
        return f"{num} (decimal) = {bin(num)} (binary) and {n}th bit is ALREADY unset"                                  

Most important part of this trick is num & ~(1 << n) operation. It turns all bits on except the targetted one.

 

Inverting every bit of a number/One’s complement operator (~): If we want to invert every bit of a number i.e change bit ‘0’ to ‘1’ and bit ‘1’ to ‘0’.We can do this with the help of ‘~’ operator. 

~1           1111 1110
~(1 << 1)    1111 1101
~(1 << 2)    1111 1011
~(1 << 3)    1111 0111
~(1 << 4)    1110 1111
~(1 << 5)    1101 1111
and so on...

num = 7                                                                  

# Inverting every bit of number num                          

print(~num)                     output: -8                                                  

Two’s complement of the number:                                                     

num = 5                                                                              

twos_complement = -num                                                          

print(f"This is two's complement {twos_complement}")                            

print(f"This is also two's complement {~num + 1}")                               

Stripping off the lowest set bit:     X = X & (X - 1)                                                    

(X-1)  inverts all the bits till it encounters the lowest set ‘1’ and it also inverts that lowest set ‘1’.  After ‘ANDing’ X with X-1 we get the lowest set bit stripped. (Brian Kernighan’s Algorithm:   n := n&(n-1)

def strip_last_set_bit(num):                          

    num &= (num - 1)                              

    return num                                  

print( strip_last_set_bit(7))               output: 6                 

For example;                                                                                                               
                            1001 1100   (num)                              
                            1001 1011   (num - 1)                                                     
                         & --------------------------                                                            
                            1001 1000  ---------> rightmost 1-bit is turned off                                      

 

Getting the lowest set bit of a number:    X &(-X)

For Example:   X = 00101100. So ~X(1’s complement) will be ‘11010011’ and 2’s complement will be (~X+1 or -X) i.e.  ‘11010100’. So if we ‘AND’ original number ‘X’ with its two’s complement which is ‘-X’, we get the lowest set bit. 

def lowest_set_bit(num):                                    

    num &= (-num)                              

    return num                                                                     

print(lowest_set_bit(10))                      output: 2

  For Example:        1011 1100   (num)                           
                      0100 0100   (-num)                           
                    & ----------------                         
                      0000 0100  --> isolated rightmost 1-bit                                   

num & (-num) does the isolation. We are going to use Two’s Complement for negative numbers  method to be able to calculate -num.  In Two’s Complement, -num = ~num + 1 so adding +1 because Two’s Complement rules makes the trick here.

~num & (num + 1) does the isolation. It finds the rightmost zero, turns other bits to 0, and sets the isolated bit to 1.

def isolate_rightmost_0bit(num: int) -> str:                                                                        
    isolated_number = ~num & (num + 1)                                                                          
    return f"Rightmost 0-bit in {bin(num)} is isolated and the result: {bin(isolated_number)}"

For Example;                      0100 0011   (~num)                                
                                          1011 1101   (num + 1)                          
                                      & ---------------------------------                                       
                                          0000 0001  --> rightmost 0 (zero) is isolated

def turn_on_rightmost_0bit(num: int) -> str:                                               
    rightmost_0bit_turned_on = num | (num + 1)                                          
    return f"Rightmost 0-bit in {bin(num)} is turned on and the result: {bin(rightmost_0bit_turned_on)}"

num | (num + 1) trick turns on the rightmost 0-bit.

For Example;                           1010 1011   (num)                                       
                                                1010 1100   (num + 1)                                              
                                              | --------------------------------
                                                1010 1111  ------------> rightmost 0 (zero) turned on                              

Division by 2 and Multiplication by 2 are very frequently that too in loops in Competitive Programming so using Bitwise operators can help in speeding up the code.  Divide by 2 using the right shift operator:

00001100 >> 1 (00001100 is 12)
------------
    00000110 (00000110 is 6)   

print(14 >> 1)               output: 7                          

Multiply by 2 using the left shift operator:                                               

print(7 << 1)                     output: 14                                                                 

 

5. The integer is even or odd:                                                           

An integer is odd if and only if the least significant bit (LSB) is 1. By using AND (&) operator between given number (num) 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

def even_or_odd(num: int) -> str:                                   
    if (num & 1) == 0:                                               
        return f"{num} is EVEN"                          
    else:                                                        
        return f"{num} is ODD"                                                    

 

6. Upper case English alphabet to lower case:   ch |= ' '                                              

The bit representation of upper case and lower case English alphabets are 

A -> 01000001          a -> 01100001
B -> 01000010          b -> 01100010
C -> 01000011          c -> 01100011
  .                               .
  .                               .
Z -> 01011010          z -> 01111010

As we can see if we set 5th bit of upper case characters, it will be converted into lower case character. We have to prepare a mask having 5th bit 1 and other 0 (00100000).  We have to prepare a mask having 5th bit 1 and other 0 (00100000). This mask is bit representation of space character (‘ ‘). 

ch = ‘A’ (01000001)           mask = ‘ ‘ (00100000)             ch | mask = ‘a’ (01100001)                            

7.  Lower case English alphabet to upper case:  ch &= '_’                                                  

 We have to prepare a mask having 5th bit 0 and the other 1 (11011111). This mask is a bit representation of the underscore character (‘_‘). The character ‘ch’ then AND with mask. 

ch = ‘a’ (01100001)     mask = ‘_ ‘ (11011111)           ch & mask = ‘A’ (01000001)                                 

 

Bits manipulation tactics                                                                  

1. Compute XOR from 1 to n                                                                                

def computeXOR(n):                                 

    uni = 0                           

    if n==0:                    

        return 0                                                                  

    for i in range(1,n+1):                       

        uni = uni ^ i                             

    return uni                                 

Efficient method:                                                                                       

When we do XOR of numbers, we get 0 as the XOR value just before a multiple of 4. This keeps repeating before every multiple of 4. 

  • x = 0, then the answer is n.                        
  • x = 1, then answer is 1.                        
  • x = 2, then answer is n+1.                                   
  • x = 3, then answer is 0.                                                                      

def computeXOR(n):                           

    if (n % 4 is 0):                            

        return n                         

    if (n % 4 is 1):                           

        return 1                          

    if (n % 4 is 2):                         

        return n + 1                                  

    else:                               

        return 0                                                                                            

Time Complexity: O(1)            Auxiliary Space: O(1)

 

2. Count of numbers (x) smaller than or equal to n such that n+x = n^x:

The count of such numbers x can be counted using the following mathematical trick. The count = pow(2, count of zero bits).

def countValues (n):                        

    count = 0                               

    for i in range(n + 1):                        

        if ((n + i) == (n ^ i)):                       

            count += 1                                       

    return count                                      

3. A number is a power of 2:                                                                  

If a number N is a power of 2, then the bitwise AND of N and N-1 will be 0. But this will not work if N is 0. So just check these two conditions, if any of these two conditions is true.

def isPowerOfTwo(x):                                                               

  # First x in the below expression is  for  the case when x is 0 

  return x and (not(x & (x - 1)))                                                    

4. Find XOR of all subsets of a set                                                                                 

We can do it in O(1) time. The answer is always 0 if the given set has more than one element. For sets with a single element, the answer is the value of the single element. 

def findXOR(Set, n):                                     

    # XOR is 1 only when   n is 1, else 0                    

    if (n == 1):                              

        return Set[0]                           

    else:                                     

        return 0                                    

arr= [1, 2, 3]                                    

print("XOR of XOR's of all subsets is ",findXOR(arr, 3))                             

Output: XOR of XOR's of all subsets is 0                                                  

Time Complexity: O(1)            Auxiliary Space: O(1)                                   

5. The Quickest way to swap two numbers:                                                       

Two numbers can be swapped easily using the following bitwise operations: a ^= b

6.   Check if a number has bits in an alternate pattern:                                                  

We can quickly check if bits in a number are in an alternate pattern (like 101010).  Compute bitwise XOR (XOR denoted using ^) of n and (n >> 1). If n has an alternate pattern, then n ^ (n >> 1) operation will produce a number having all bits set.

 

Conclusion                                                                                            

Bitwise Operations decrease the time, and space complexity of code on a high scale. There are many logics and implementations that can be done very easily using bitwise operations. Bitwise Operations are heavily used in compression and Encryption.  In the Connection medium, checksum, parity bits, stop bits, and flow control algorithms all use bitwise encryption and compression process since the medium is capable of transferring data in bits. Checksum and Cyclic Redundancy Check (CRC) uses bits for the error detection process when data is transferred through a medium. The flow of data in electronic machines is in the form of bits. These machines use logic gates which are designed to maintain the flow of signals, data, and processes through a system. The microprocessor is an example of this system. This device is completely designed on the bitwise operators and operations.

Digital image processing uses bitwise operations on image pixels. To enhance the image, to view the different sections of the microscopic image, the image is captured by the satellites and telescopes of the outer space. Bitwise Operations are performed on these images to see a clear view, or to extract the different sections of the images.

If you want to become a competitive programmer, then you had to have well versed in bitwise operations. Bitwise Operations decrease the time, and space complexity of code on a high scale. There are many logics and implementations that can be done very easily using bitwise operations.


Responses(0)