How I can remove all odds bits in C?

Question

I have int 136970250 (1000 0010 1010 0000 0000 0000 1010) -> I need to remove all odd bits(1, 3, 5, 7...)

1000 0010 1010 0000 0000 0000 1010 -> 10 0111 0000 0011 (9987) - because this bits do not have information.

How to do it?

Answer 1

How I can remove all odds bits...?
I need to remove all odd bits(1, 3, 5, 7...)

OP's single example looks like retaining the odd bits, given that the least significant bit is usually bit 0.

This answers assumes code needs to retain the even bits and discard the odd ones. It is easy to adjust the algorithm to retain other bits.

---

Rather than a loop of 32 iterations, shift bits in groups. First pair-up required bits, then in groups of 4, then in groups of 8, etc.

Say we want to retain bits 0b .a.b .c.d .e.f .g.h .i.j .k.l .m.n .o.p

uint16_t IK_RemoveOddBits(uint32_t x) {
  // x = 0b .a.b .c.d .e.f .g.h .i.j .k.l .m.n .o.p

  x = ((x & 0x44444444) >> 1) | ((x & 0x11111111) >> 0);
  // x = 0b ..ab ..cd ..ef ..gh ..ij ..kl ..mn ..op

  x = ((x & 0x30303030) >> 2) | ((x & 0x03030303) >> 0);
  // x = 0b .... abcd .... efgh .... ijkl .... mnop

  x = ((x & 0x0F000F00) >> 4) | ((x & 0x000F000F) >> 0);
  // x = 0b .... .... abcd efgh .... .... ijkl mnop

  x = ((x & 0x00FF0000) >> 8) | ((x & 0x000000FF) >> 0);
  // x = 0b .... .... .... .... abcd efgh ijkl mnop

  return x;
}

To remove even bits, amend above code by adding a x >>= 1 or simply

uint16_t IK_RemoveEvenBits(uint32_t x) {
  return IK_RemoveOddBits(x >> 1);
}

Tip: Best to use unsigned types when coding these shift type problems. No need to extend the sign bit of signed integers.

Answer 2

1. Make a new integer, initialize it to 0

2. Iterate with a for loop from 0 to half the number of bits in the original integer (non-inclusive)

3. For each run through the loop, AND the original integer with (1 << (i * 2)). If it's nonzero, OR the new integer with (1 << i)

4. Finis

EDIT: Looking at the example again, it looks like what you actually want is to remove all the even bits, not the odd ones. So for that, just AND the original integer in step 3 with (1 << (i * 2 + 1)) instead.

EDIT 2: From your example, it appears you're working with 32-bit integers, but just to cover all bases, I'm going to add that if your integer is actually 64-bit, you should replace 1 with 1ULL in step 3.

Answer 3

The odd bits can be removed (assuming they are zeroed out) in a few bit_permute_steps (see below), such as this:

x = bit_permute_step(x, 0x22222222, 1);  // Bit index swap 0,1
x = bit_permute_step(x, 0x0c0c0c0c, 2);  // Bit index swap 1,2
x = bit_permute_step(x, 0x00f000f0, 4);  // Bit index swap 2,3
x = bit_permute_step(x, 0x0000ff00, 8);  // Bit index swap 3,4

(generated by calcperm)

This can easily be extended to 64bits by widening the constants and adding an extra step. If you want to remove the even bits you can just shift right by 1 first.

The definition of bit_permute_step is

t_bits bit_permute_step(t_bits x, t_bits m, t_uint shift) {
  t_bits t;
  t = ((x >> shift) ^ x) & m;
  x = (x ^ t) ^ (t << shift);
  return x;
}

With suitable types used.

For modern Intel processors (and Ryzen, but it is slow there) a more built-in solution is using _pext_u32 with a mask of all the bits you want to keep.