1

Assume I have a number and I want to interpret every other bit as a new number, e.g.

uint16_t a = 0b1111111000000001;
uint16_t mask = 0xAAAA; // 0b1010101010101010

I now want to be able to get every other bit packed into two 8 bit variables, like

uint8_t b = a & mask ... //  = 0b11110000
uint8_t c = a & ~mask ... // = 0b11100001

Is there an efficient way of accomplishing this? I know that I can loop and shift but I am going to do this for a lot of numbers. Even better if I can get both b and c at the same time.

Noxet
  • 236
  • 4
  • 16
  • 1
    I have no idea what you are trying to do. 0xFF & 0xAA is 0xAA. It is not 0xF0. Start by dropping the binary notation, it is confusing. – Lundin Mar 18 '19 at 15:57
  • 1
    @Lundin he tries to implement the `Compress` function from Hacker's delight. However, in his question he expresses bigger expectations then it's possible to do. – alinsoar Mar 18 '19 at 16:06
  • You are trying to put the result into a ```uint8_t``` variable, but your initial values are of type ```uint16_t```The compiler would do some casting and you will lose the data. – vasile_t Mar 18 '19 at 16:17
  • Possible duplicate of [How to print unsigned char as 2-digit hex value in C?](https://stackoverflow.com/questions/12344814/how-to-print-unsigned-char-as-2-digit-hex-value-in-c) – vasile_t Mar 18 '19 at 16:42
  • @alinsoar How does the compress function work? Do you have a reference? I only find compression algorithms.. – Noxet Mar 19 '19 at 09:51
  • @vasile_t Yes, I want to extract every other bit and squeeze them together into a new smaller number – Noxet Mar 19 '19 at 09:51
  • 1
    @Noxet Hacker's delight – alinsoar Mar 19 '19 at 09:52
  • @alinsoar Ah yes, thank you. That is what I was looking for :D – Noxet Mar 19 '19 at 09:55

1 Answers1

1

You can precompute some tables if you want to avoid too much shifting.

I do it for a&mask. For the other situation it is identical with a&~mask.

First, you do a& mask to drop the 1's on the unused positions of a.

Suppose you have a=a1 0 a2 0 a3 0 a4 0. You want to get the number a1 a2 a3 a4. There are not many possibilities.

You can have a precomputed vector V of short integers and associate for each entry the corresponding value.

For example, v[0b10100010] will be 13, if the mask is 0b10101010.

If the precomputed vector is not too large it will stay in cache L1, so it will be very fast, for example, if you split your number in groups of 8 or 16 bits.

alinsoar
  • 15,386
  • 4
  • 57
  • 74
  • This is a very good idea. The code has to be really fast, and a lookup table might be my best option here. – Noxet Mar 19 '19 at 10:04