Extract Even Bits Only from 32-bit Register

O(1)

#include <stdio.h>
#include <stdint.h>

uint32_t extract_even_bits(uint32_t reg) {
    uint32_t even_bits = reg & 0x55555555;
    even_bits = (even_bits | (even_bits >> 1)) & 0x33333333;
    even_bits = (even_bits | (even_bits >> 2)) & 0x0F0F0F0F;
    even_bits = (even_bits | (even_bits >> 4)) & 0x00FF00FF;
    even_bits = (even_bits | (even_bits >> 8)) & 0x0000FFFF;
    return even_bits;
}

int main() {
    uint32_t reg;
    scanf("%u", &reg);
    printf("%u", extract_even_bits(reg));
    return 0;
}

Solving Approach

1. Masking Even Bits:
   The process starts by applying a mask (0x55555555) to the input value. This mask has binary 1s at all even positions (0, 2, 4, ..., 30) and 0s elsewhere. By performing a bitwise AND with this mask, we isolate the even bits and set all odd bits to zero.

2. Packing the Bits:
   After masking, the even bits are still spaced out within the 32-bit value. To compress them into consecutive positions, we use a sequence of bitwise ORs and ANDs combined with right shifts. Each step moves the bits closer together:

   • The first step combines each pair of bits, then masks to keep only the relevant pairs.
   • The next steps repeat this process for groups of four, eight, and finally sixteen bits.
   • After each shift and mask, the bits are packed more tightly, until all even bits occupy the lower 16 bits of the result.

3. Result:
   The final value contains the original even-positioned bits, now packed together in order, starting from the least significant bit. This approach is highly efficient because it uses a fixed number of operations, regardless of the input, and avoids any loops.

Here’s a step-by-step trace of the even_bits variable for reg = 0b01010101 (decimal 85):

Initial value

reg = 0b01010101

Step 1: Mask Even Bits

even_bits = reg & 0x55555555;

• 0x55555555 = 01010101 01010101 01010101 01010101
• For 8 bits: 01010101

even_bits = 0b01010101

Step 2: First Packing

even_bits = (even_bits | (even_bits >> 1)) & 0x33333333;

• even_bits >> 1 = 00101010
• even_bits | (even_bits >> 1) = 01111111
• 0x33333333 = 00110011 00110011 00110011 00110011
• For 8 bits: 00110011
• 01111111 & 00110011 = 00110011

even_bits = 0b00110011

Step 3: Second Packing

even_bits = (even_bits | (even_bits >> 2)) & 0x0F0F0F0F;

• even_bits >> 2 = 00001100
• even_bits | (even_bits >> 2) = 00111111
• 0x0F0F0F0F = 00001111 00001111 00001111 00001111
• For 8 bits: 00001111
• 00111111 & 00001111 = 00001111

even_bits = 0b00001111

Step 4: Third Packing

even_bits = (even_bits | (even_bits >> 4)) & 0x00FF00FF;even_bits >> 4 = 00000000

• even_bits | (even_bits >> 4) = 00001111
• 0x00FF00FF = 00000000 11111111 00000000 11111111
• For 8 bits: 11111111
• 00001111 & 11111111 = 00001111

even_bits = 0b00001111

Step 5: Final Packing

even_bits = (even_bits | (even_bits >> 8)) & 0x0000FFFF;

• even_bits >> 8 = 00000000
• even_bits | (even_bits >> 8) = 00001111
• 0x0000FFFF = lower 16 bits set
• 00001111 & 00001111 = 00001111

even_bits = 0b00001111

Final Output:
0b1111 (decimal 15)