Bit Operations

Bit manipulation allows us to perform operations directly on the binary representation of numbers, leading to efficient and elegant solutions.

Why Bit Manipulation?

• Efficiency: Bit operations are extremely fast.
• Memory: Can represent multiple boolean states in a single integer.
• Common Use Cases: Permissions, flags, cryptography, compression, optimization problems.

---

Common Bit Operations

1. Check if K-th bit is set

To check if the K-th bit (0-indexed from right) is set:

fun isKthBitSet(n: Int, k: Int): Boolean = (n and (1 shl k)) != 0

2. Set K-th bit

To set the K-th bit:

fun setKthBit(n: Int, k: Int): Int = n or (1 shl k)

3. Clear K-th bit

To clear the K-th bit:

fun clearKthBit(n: Int, k: Int): Int = n and (1 shl k).inv()

4. Toggle K-th bit

To flip the K-th bit:

fun toggleKthBit(n: Int, k: Int): Int = n xor (1 shl k)

5. Toggle rightmost set bit

To toggle (unset) the rightmost set bit:

fun toggleRightmostSetBit(n: Int): Int = n xor (n and -n)

6. Isolate rightmost set bit

To get a number with only the rightmost set bit:

fun isolateRightmostSetBit(n: Int): Int = n and -n

7. Is power of 2

Check if a number is a power of 2:

fun isPowerOfTwo(n: Int): Boolean = n > 0 && (n and (n - 1)) == 0

8. Modulo (Power of 2)

Efficient modulo when divisor is a power of 2:

fun moduloPowerOfTwo(n: Int, k: Int): Int = n and (k - 1) // k must be power of 2

9. Count set bits (Brian Kernighan's Algorithm)

Count the number of 1s in the binary representation:

fun countSetBits(n: Int): Int {
    var count = 0
    var num = n
    while (num != 0) {
        num = num and (num - 1)
        count++
    }
    return count
}