Given a number N and an integer K, the task is to set the Kth bit of the number N, i.e., if the Kth bit is 0, then set it to 1 and if it is 1 then leave it unchanged.
Examples:
Input: N = 5, K = 2
Output: 7
Explanation:
5 is represented as 101 in binary and has its second bit 0, so setting it will result in 111 i.e. 7.Input: N = 5, K = 1
Output: 5
Explanation:
5 is represented as 101 in binary and has its first bit is already 1, so setting it will result in 101 i.e. 5.
Naive Approach: A simple approach would be to add the 2’s pow if that bit is not set in number. Following are steps for our idea.
- Check if bit is set or not.
N = 4, K = 1
5 -> 100
so if take the bitwise and of N and 2K-1 if that bit is set it result 1 else it result 0.
since 1 & 0 = 0 and 0 & 1 = 0
1 & 1 = 1 and 0 & 0 = 1
K = 1 -> 21-1 = 20 = 1 -> 001
N & 2k-1 = 100 & 001 = 000 so bit is not set.
- If bit is not set then set the bit with the adding 2K-1 to the number.
N = 4 -> 100 , K = 20 = 1
N + K = 4 +1 = 5
So we set the 1’s bit and result is 5 -> 101
- If bit is set then do not add number.
Below is the program to implement the above idea.
C
// Online C compiler to run C program online#include <stdio.h>#include<math.h>// Function to set Kth bitint number( int n, int k){ int x = (int)pow(2,k-1); // Checking the Kth bit is set or not if(n & x) return n; else{ return n + x; }}// Driver codeint main() { int result = number(5, 2); printf("%d",result); return 0;} |
7
Time Complexity: O(log k)
Auxiliary Space: O(1)
Effective Approach: The approach to solve this problem is based on bitmasking technique with help of bitwise OR operator.
- Since bitwise OR of any bit with a set bit results in a set bit, i.e.
Any bit <bitwise OR> Set bit = Set bit
which means,
0 | 1 = 1
1 | 1 = 1
- So for setting a bit, performing a bitwise OR of the number with a set bit is the best idea.
n = n | 1 << K
OR
n |= 1 << K
where K is the bit that is to be set
Below is the C++ program to implement the above approach-
C++
// C++ program to implement the above approach#include <stdio.h>// Function to set the// kth bit of nint setBit(int N, int K){ return (N | (1 << (K - 1)));}// Driver codeint main(){ int N = 5, K = 2; printf("%d\n", setBit(N, K)); return 0;} |
Time Complexity: O(1)
Auxiliary Space: O(1)
7
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
