Bit Manipulation

Operand 1	Operand 2	Result
0	0	0
0	1	0
1	0	0
1	1	1

Operand 1	Operand 2	Result
0	0	0
0	1	1
1	0	1
1	1	1

Operand 1	Operand 2	Result
0	0	0
0	1	1
1	0	1
1	1	0

Operand	Result
~ 0	1
~ 1	0

Operand	SHIFT	Result
0101 (5)	<< 1	1010 (10)
0011 (3)	<< 2	1100 (12)

Operand	SHIFT	Result
1010 (10)	>> 1	0101 (5)
1100 (12)	>> 2	0011 (3)

Operand	SHIFT	Result
1010 (-6)	>> 1	1101 (-3)
0110 (6)	>> 1	0011 (3)

Two's Complement

Integers (including negative numbers) are stored using two's complement representation. Two's complement is a mathematical method and binary encoding system used in computers to represent both positive and negative integers using binary numbers.

It is the most common system for representing signed integers in binary on modern computers.

Why Two’s Complement?

Simplifies arithmetic: Addition and subtraction work the same for positive and negative numbers.
Provides a unique representation for zero.
It lets computers store negative numbers without needing a separate sign bit.

base 10 to base 2

1. Convert base 10 Integer to base 2 Integer

Base 2 Addition

2. Add Two Binary Strings

base 2 to base 10

3. Convert Binary to Decimal

Decimal to Hexadecimal

4. Design an algorithm that returns the hexadecimal representation of a base10 integer.

Scenario	Best Case	Worst Case	Edge Case
Parameters	n = 0	n = 255	n = -10
Output	"0"	"ff"	"Negative not supported"
Explanation	Zero, O(1) time	Large number, O(log n) time	Negative, immediate return

Power of 2

5. Design an algorithm that returns '1' if a given positive integer 'x' is a power of '2' else returns '0'.

Parameters - (Integer)
Output - '1' or '0' as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	x = 4	x = 6	x = 0
Output	1	0	0
Explanation	Power of 2, O(1) time	Not a power of 2, O(1) time	Zero/negative, immediate 0

Number of Set Bits

6. Design an algorithm that returns the count of set bits in the binary representation of a positive integer 'x'.

Parameters - (Integer)
Output - count as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	x = 1	x = 15	x = 0
Output	1	4	0
Explanation	Single bit, O(1) iterations	All bits set, O(log x)	Zero, immediate 0

Unpaired Element

7. Design an algorithm that returns the only element that appear only once (unpaired) in an array of integers.

The rest of the elements appear exactly twice in the array.

Parameters - (Array of integers)
Output - Element as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	A = [1,1,2,2,3]	A = [1,1,2,2,3,3,4]	n = []
Output	3	4	0
Explanation	Small array, O(n) time	Large array, O(n) time	Empty array, returns 0

Even or Odd

8. Design an algorithm that checks if a given integer 'x' odd or even.

The algorithm should return '0' if the integer is even and '1' if it is odd.

Parameters - (Integer)
Output - 1 or 0 as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	x = 2	x = 3	x = 0
Output	0	1	0
Explanation	Even, O(1) time	Odd, O(1) time	Zero (even), O(1) time

Swap a and b

9. Given two variables 'a' and 'b' assigned with distinct integer values. Design an algorithm that swaps and returns the integer value of a and b.

Parameters - (integer a), (integer b)
Output - Updated values of 'a' and 'b' as per above statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	a = 1, b = 2	a = 100, b = 200	a = 0, b = 1
Output	[2, 1]	[200, 100]	[1, 0]
Explanation	Small values, O(1) time	Large values, O(1) time	Zero and non-zero, O(1) time

Rightmost set bit

10. Design an algorithm that find the position of the least significant bit set to '1' in the binary representation of a given integer 'n'.

Least Significant Bit is the rightmost bit in the binary representation of a number.

Parameters - (Decimal representation of Integer)
Output - Position of set bit as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	1	1073741824	0
Output	1	1000000000000000000000000000000 , 31	Undefined / Error
Explanation	The number 1 has its only set bit at position 1, requiring minimal computation.	The set bit is at the far left (31st position), requiring maximum computation for log-based approaches.	No set bit exists, so handling this edge case is necessary (returning 0 or an error message).

Unpaired Element 2

11. From an array of integers where all the numbers appear exactly twice, except for two unique elements that appear only once.

Design an algorithm that finds the two unique elements appearing only once.

parameters - (Array of Integers)
Output - elements as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[1, 2, 3, 1, 2, 4]	[10, 20, 30, 40, 50, 60, 10, 20, 30, 40]	[5, 7]
Output	[3, 4]	[50, 60]	[5, 7]
Explanation	The unique elements appear early in the array, making the algorithm efficient. Minimal operations are needed.	The unique elements appear at the end of a large array, requiring a full traversal and extra bitwise operations.	The array has only two elements, both unique, making it the smallest valid input case. The algorithm must still correctly identify them.

Odd Number of Times

12. From an array of integers where all elements appear an even number of times, except for two distinct numbers that appear an odd number of times.

Design an algorithm that returns the two distinct numbers appearing odd number of times.

parameters - (Integer Array)
output - elements as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[1, 2, 3, 1, 2, 4]	[100, 200, ..., 10000, 50001, 70003]	[1000001, 1000001, 9999999, 8888888]
Output	[3, 4]	[50001, 70003]	[9999999, 8888888]
Explanation	The array is small and already sorted, making it easy to find the two unique numbers.	The array is large and unsorted, requiring an efficient approach like bitwise XOR to avoid O(n²) complexity.	Large numbers in the array should still be handled efficiently.

One Odd Number of Times

13. Design an Algorithm that returns the only element in an array that appears an odd number of times, while all the other elements appear an even number of times.

parameters - (Integer Array)
output - element as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[7]	[1, 2, 1, 2, ..., 999999, 500001]	[10, 10, 10]
Output	7	500001	10
Explanation	The array contains only one element, making it trivial to find the odd-occurring number.	The array is very large (millions of elements), requiring an efficient approach (e.g., XOR) to avoid O(n²) complexity.	The array contains only one unique number, but it appears an odd number of times.

Bitwise AND

1. Design an algorithm that computes the Bitwise AND of all the integers between L and R (inclusive) in an integer array.

parameters - (Integer Array), (i), (j)
output - computation as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[5, 7, 8, 10], i = j = 2	Large array (e.g., 10⁶ elements), i = 0, j = n-1	[1, 1, 1, 1], i = 0, j = 3
Output	78	0 (in most cases)	1
Explanation	When i == j, only one number is considered, and the result is the number itself.	The algorithm has to compute the AND for all elements, which is computationally heavy. If at least one number in the range has a 0 bit at any position, the result will be 0.	All elements are 1, so AND operation does not change the values.

Maximum XOR

2. Design an algorithm that returns the two element in an integer array whose Bitwise XOR is maximum possible among all pairs in the array.

parameters - (integer array)
output - array elements as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[1, 2, 4, 8, 16, 32, 64]	[1023, 1022, 1021, ..., 1]	[0, 0, 0, 0, 0] / [1, 1] / [2147483647, 0]
Output	[32, 64] (or another optimal pair)	[1023, 0]	[0, 0] / [1, 1] / [2147483647, 0]
Explanation	Numbers are powers of 2, ensuring large XOR values, making it easy to determine the best pair.	A descending sequence makes it harder to find the optimal pair, requiring O(n log m) operations if using a Trie-based approach.	Edge cases include all elements being identical (XOR = 0), only two identical numbers, or a mix of extreme values like 0 and max 32-bit int.

Maximum AND

3. Design an algorithm that returns the two elements inan integer array whose Bitwise AND is maximum possible among all pairs in the array.

parameters - (integer array)
output - array elements as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[1024, 2048, 4096, 8192, 16384]	[1, 3, 7, 15, 31]	[0, 0, 0, 0, 0] / [1, 1] / [2147483647, 0]
Output	[8192, 16384] (or another optimal pair)	[1, 3] (producing lowest possible AND values)	[0, 0] / [1, 1] / [2147483647, 0]
Explanation	Numbers are powers of 2, ensuring large XOR values, making it easy to determine the best pair.	A sequence of consecutive numbers contains mostly 1s in lower bits but fewer common high bits, leading to minimal AND results.	Edge cases include all elements being identical (AND remains the same), only two identical numbers, or a mix of extreme values like 0 and max 32-bit int.

All Possible Subsets

4. Design an algorithm that generates all possible subsets of the array (including the empty subset and the array itself).

parameters - (Integer Array)
output - subsets as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[1, 2, 3] (small array)	[1, 2, 3, ..., 20] (large array)	[] (empty array) / [5] (single element)
Output	[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]	Large number of subsets (2^n complexity)	[[]] for empty array, [[ ], [5]] for single element
Explanation	The number of subsets is small (2³ = 8 subsets).	The number of subsets grows exponentially (2²⁰ = 1,048,576 subsets).	The function should still return valid subsets even for edge cases.

Binary Bit Reversal

5. Design an algorithm that reverses the bits of a given 32-bit unsigned integer and returns the resulting integer.

parameters - (32-bit unsigned integer)
output - 32-bit unsigned integer as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	n = 0 (00000000000000000000000000000000)	n = 4294967295 (11111111111111111111111111111111)	n = 2863311530 (10101010101010101010101010101010)
Output	0 (00000000000000000000000000000000)	4294967295 (11111111111111111111111111111111)	1431655765 (01010101010101010101010101010101)
Explanation	All bits are 0, so reversing doesn't change anything.	All bits are 1, so reversing doesn't change anything, but the algorithm still processes all bits.	Alternating bit patterns to verify if bit shifting logic correctly preserves positions.

Greater Power of 2

6. Design an algorithm that returns the smallest power of 2 that is greater than given integer 'n'.

If n is already a power of 2 return as default n.

parameters - (integer n)
output - integer as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	n = 8 (already a power of 2)	n = 2^x - 1 (e.g., 31, 63, 127)	n = 0 or negative (-5, -1)
Output	8	32, 64, 128	1
Explanation	Since n is already a power of 2, it is returned immediately in 𝑂 ( 1 ) O(1) time.	The algorithm iterates multiple times to find the next power of 2, leading to 𝑂 ( log ⁡ 𝑛 ) O(logn) complexity.	Since power of 2 cannot be negative, we return 1 as the smallest power of 2.

Power of 4

7. Design an algorithm that returns '1' if a given integer 'n' is a power of 4 else returns '0'.

parameters - (integer)
output - 1 or 0 as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	n = 1	n = 2^{31} - 1	n = -4
Output	1	0	0
Explanation	1 is 4^0 , which is a power of 4. This is the quickest check.	Checking a large number that is not a power of 4 requires evaluating bitwise conditions.	Negative numbers cannot be powers of 4.

Missing Number 0 to n

8. Design an algorithm that determine the only one missing number in an unordered array containing n unique numbers from [0, n].

parameters - (Integer Array)
output - integer as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[0, 1, 2, 3, 5] (ordered but missing 4)	[3, 0, 1, 4, 2] (unordered, missing 5)	[0] (Only one element, missing 1)
Output	4	5	1
Explanation	The array is sorted except for the missing number, making it easy to find.	The numbers are shuffled, requiring a complete scan or advanced techniques.	The array has the first element but is missing the last.

Two Missing Number 1 to n

9. Design an algorithm that returns the only two missing numbers in an unordered array containing n-2 unique integers from the range [1, n].

parameters - (Integer Array)
output - integers as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[1, 2, 3, ..., n-2] (All numbers in order except the last two missing)	[2, 4, 6, ..., n] (Numbers are scrambled, and missing numbers are somewhere in between)	[1, 3, 4, 5, ..., n] (Missing values are not adjacent)
Output	(n-1, n)	(x, y)	(2, x)
Explanation	The two largest numbers are missing, and their sum can be computed efficiently.	The missing numbers are randomly placed, requiring full calculations.	The missing numbers are scattered throughout the sequence, requiring extra checks.

Missing and Duplicate

10. Given an unordered array of n elements containing unique numbers from 1 to n, but one number is missing and one number appear twice.

Design an algorithm that returns the missing number and the duplicate number.

parameters - (integer array)
output - integers as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	[1, 2, 3, 4, 5, 5]	[1, 1, 2, 3, 4, 5]	[6, 1, 3, 3, 4, 5]
Output	(5, 6)	(1, 6)	(3, 2)
Explanation	The duplicate and missing numbers appear at the end of the array, making detection straightforward.	The duplicate is at the start, requiring a full scan to detect the missing number.	The numbers are unsorted, making detection harder.

Hamming Distance

11. Given two integers x and y, design an algorithm that determines the hamming distance between them.

The Hamming Distance between two numbers is defined as the number of positions at which their corresponding bits are different.

parameters - (integer x), (integer y)
output - bit positions as per above problem statement

Scenario	Best Case	Worst Case	Edge Case
Parameters	x = 0, y = 0	x = 0, y = 2³¹-1	x = 15, y = 0
Output	0	31	4
Explanation	Both numbers are identical, so no differing bits.	One number is all 0s, and the other is all 1s, leading to maximum bit differences.	15 (1111) and 0 (0000) differ in all 4 bits.

- Fundamentals -

Bitwise Operations -

1. AND(&) Table

2. OR (|) Table

3. XOR(^) Table

4. NOT (~) Table

5. Left Shift Table

6. Right Shift Table