Last Updated: 8 Dec, 2020
Toggle K bits
Easy
Asked in company
You are given a 32-bit integer ‘N’. Your task is to toggle the rightmost ‘K’ bits in the given integer and return the new integer.
For Example :
If ‘N’ = 12 and ‘K’ = 2:
The binary representation of 12 is ‘1100’, after toggling rightmost 2 bits, it becomes ‘1111’ i.e. 15. Hence, the answer is 15.
Input format :
The first line contains a single integer T representing the number of test cases.
The first and only line of each test case contains two space-separated integers ‘N’ and ‘K’ that represent the given 32-bit integer and number of rightmost bits to toggle respectively.
Output format :
For each test case, return the new Integer after toggling the rightmost ‘K’ bits.
Note:
You don’t need to print anything, it has already been taken care of. Just implement the given function
Follow Up:
Can you solve this using O(1) time complexity?
Constraints:
1 <= T <= 10
1 <= N <= 10^9
1 <= K <= 31
Time Limit: 1 sec
Approaches
The idea is to simply iterate through the rightmost ‘K’ bits and toggle them one by one using the XOR operator.
Here is the algorithm:
- Run a loop from 0 to ‘K’-1 (say iterator ‘i’):
- Update ‘N’ = ‘N’ xor (1 << (‘i’)). This is done to toggle the ‘i-th’ bit.
- Return ‘N’.
The idea is to first extract the rightmost ‘K’ and toggle them. Then, after clearing the rightmost ‘K’ bits from the original integer, storing the toggled bits back into the original integer.
Here is the algorithm:
- Extract the rightmost ‘K’ bits and store them into a variable (say ‘lastKbits’). Hence, ‘lastKbits’ = ‘N’ & ((1<<’K’)-1).
- ‘N’ = ‘N’ & ~((1<<’K’)-1) (Clearing rightmost ‘K’ bits from ‘N’).
- ‘lastKbits’ = (negation of (lastKbits)) & ((1<<’k’)-1). (Toggling rightmost ‘K’ bits of ‘lastKbits’).
- ‘N’ = ‘N’ + ‘lastKbits’. (adding toggled bits to ‘N’).
- Return ‘N’.