Problems/Bit Manipulation/Swap Odd and Even Bits
Bit Manipulation
easy

Swap Odd and Even Bits

This problem focuses on bit manipulation, a crucial skill for optimizing performance and understanding low-level system architecture. The task is to rearrange the bits of an integer by interleaving two new numbers created by its even and odd bits.

bit-manipulationbitmaskingoptimizationinterview-question

Problem Statement

Given a 32-bit unsigned integer, rearrange its bits such that the bits at even indices are placed into a new integer, and the bits at odd indices are placed into another new integer. Then, interleave the bits of these two new integers, starting with the least significant bit of the 'even' integer, to form a final result. Return the final 32-bit unsigned integer.

Example 1
Input: 10 (Binary: 00000000000000000000000000001010)
Output: 5 (Binary: 00000000000000000000000000000101)
Even bits (0, 2) are 0 and 1, forming 01 (1). Odd bits (1, 3) are 1 and 0, forming 10 (2). Interleaving 1 and 2 creates 0101 (5).
Example 2
Input: 21 (Binary: 00000000000000000000000000010101)
Output: 42 (Binary: 00000000000000000000000000101010)
Even bits (0, 2, 4) are 1, 1, 0 forming 011 (3). Odd bits (1, 3, 5) are 0, 0, 1 forming 100 (4). Interleaving 3 and 4 creates 001010 (42).
Constraints
  • -The input is a 32-bit unsigned integer.
  • -The output must also be a 32-bit unsigned integer.
  • -You must not use any built-in functions that directly perform bit interleaving.
  • -The solution should be efficient in terms of time and space complexity.
  • -The solution must handle the case where the input is 0.

Brute Force Approach

The brute-force approach would involve iterating through each bit of the integer, identifying whether it is at an even or odd index, and constructing two new integers accordingly. This is like manually sorting marbles into two separate bins based on their position in a line. The time complexity is O(n) where n is the number of bits, and the space complexity is O(1) since we only need constant extra space for the new integers.

TimeO(1)
SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem