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: combinatorics, number theory, graph theory, algorithmic game theory, computational geometry, string 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
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
We will be using the ‘XOR’ operator here which is this ‘^’. The reason behind the ‘XOR’ operator is because of its properties.
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.
We can use ‘AND’ operator. Left shift ‘1’ to the given position and then ‘AND'(‘&’).
def at_position(num,pos):
bit = num & (1 << 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
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)
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.
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)
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)))
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)
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.
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.
