Bit Manipulation Techniques

Welcome to this quick but exciting lesson on Bit Manipulation Techniques. Bit manipulation is a powerful technique used in programming to solve problems efficiently that may initially seem complex or resource-intensive. By examining and manipulating the binary representations of data, we can develop solutions that satisfy the problem requirements and maintain good time and space complexity.

In this lesson, we'll practice techniques such as setting and clearing bits, counting set bits, and bit masking. We will be using Kotlin to illustrate these techniques. Kotlin takes a specific approach to bitwise operations: instead of using symbolic operators (like & or |), it uses infix functions such as and, or, xor, and bit shifts like shl or shr. It also provides the inv() function for bitwise inversion.

Take a look at the preview problem:

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

This function counts the number of set bits (1s) in the binary representation of a number. The and function is used for the bitwise AND operation. The num - 1 operation flips the least significant bit (the rightmost 1 bit in the binary representation) of num to 0, and num = num and (num - 1) applies this change to num. The while loop continues as long as num != 0, and with each iteration, the count is increased, tracking the number of set bits.

For example, consider n = 6, which is 110 in binary:

• n - 1 is 5 (101 in binary).
• The bitwise AND operation 110 and 101 results in 100 (which is 4 in decimal).

Now, it's time to roll up your sleeves and put these techniques into practice. Our exercises will challenge you and help deepen your understanding of bit manipulation. Remember, the goal is not only to learn how to solve specific problems but also to understand the fundamentals of bit manipulation and how to apply this knowledge to solve a wide variety of problems. Let's get started!