Turn On k'th Bit in a Number

Problem Statement

Given an integer number and an integer k, turn on (set to 1) the k-th bit of the binary representation of the number. The bit positions are indexed from 0 (rightmost bit).

Input:

• number: An integer whose k-th bit needs to be turned on.
• k: The index of the bit to be turned on.

Output:

• The integer with the k-th bit turned on.

Constraints:

• 0 ≤ number ≤ 2^31 - 1 (32-bit unsigned integer)
• 0 ≤ k < 32

Understanding the Problem

Let's say we are given an integer num and a position k. The goal is to turn on the bit at position k (0-based index) in the binary representation of num. In other words, if the bit at position k is initially 0, we want to change it to 1, while leaving the other bits is unchanged.

Examples

Example 1:

Input: number = 10 (Binary: 1010), k = 2
Output: 14 (Binary: 1110)

Explanation:

Before:
               +-----+-----+-----+-----+
 number = 10 = |  1  |  0  |  1  |  0  |
               +-----+-----+-----+-----+
           k =    3     2     1     0

After:
               +-----+-----+-----+-----+
 number = 10 = |  1  |  1  |  1  |  0  |
               +-----+-----+-----+-----+
           k =    3     2     1     0

Example 2:

Input: num = 16, k = 0
Output: 17

Explanation:
Binary of 16: 0001 0000
Mask (1 << 0): 0000 0001
Result (|): 0001 0001 -> 17

Different Approaches

1️⃣ Bit Manipulation (BitMask OR)

To accomplish this task, we can use the bitwise OR (|) operation. The idea is to create a mask with the k'th bit set to 1 and all other set to 0. Then, we perform a bitwise OR operation between the original number and the mask.

How It Works:

1. Create a mask with the k-th bit set to 1 by left-shifting 1 by k positions: 1 << k.
2. Use the OR operator (|) to turn on the k-th bit of the number. Any bit that is already 1 remains 1, and the k-th bit is set to 1 if it wasn't already.

Formula:

number = number | (1 << k);

• 1 << k creates a number where only the k-th bit is set to 1.
• | (OR) with the original number will set the k-th bit to 1 without affecting the other bits.

Dry Run:

Let's dry run the example with number = 10 and k = 2.

1. Initial Values:
   • number = 10 (Binary: 1010)
   • k = 2
2. Create Mask:
   • mask = 1 << k
   • mask = 1 << 2 = 4 (Binary: 0100)
3. Perform Bitwise OR Operation:
   • result = number | mask
   • result = 1010 | 0100 = 1110 (Binary: 14)
4. Final Output:
   • 14 (Decimal)

Code:

#include <iostream>

// Function to turn on the k'th bit in a number
int turnOnKthBit(int num, int k) {
    // Creating a mask with the k'th bit set to 1
    int mask = 1 << k;

    // Performing bitwise OR to turn on the k'th bit
    return num | mask;
}

int main() {
    // Example usage
    int num = 10;  // Binary: 1010
    int k = 2;

    int result = turnOnKthBit(num, k);

    std::cout << "Number after turning on the k'th bit: " << result << std::endl;

    return 0;
}

// Output
Number after turning on the k'th bit: 14

Complexity Analysis:

• Time Complexity:O(1) Each operation is constant time.
• Space Complexity:O(1) No extra space used.