Converting array of bits to array of hex in C through bitwise operations

Question

I'm trying to convert an array of bits to an array of bytes, except my operations seem to be reading my bits in the opposite direction from what I want them to be. For example, say the array of binary bits is 10110111 11000000 00000110. I want the byte array to be {B7, C0, 06}. Instead, my code below produces an output of of {ED, 03, 60} i.e. it reads every 8 bits in the opposite direction. Could anyone provide me some suggestions as to where I am going wrong?

void find_hex_arr(uint8_t* bit_arr, int bit_len) {
  uint8_t* hex_arr = malloc(bit_len/8);
  int index = 0;
  unsigned int i = 0;
  unsigned int j = 0;
  for (i = 0; i < bit_len; i = j) {
    for (j = i; j < i + 8; ++j) {
      hex_arr[index] |= bit_arr[j] << (j - i);
    }
    index++;
  }
}

Reduce your test case to the simplest possible input (e.g. 8 bits) then actually debug the code by running in a debugger and/or adding debug print statements. — kaylum
– kaylum, Commented May 30, 2020 at 1:39
Like all numbers, digits in a binary number goes from right to left. The rightmost digit is the least significant digit (bit 0 for binary numbers). Because of that I suggest you start at the rightmost digit and work towards the left. — Some programmer dude
– Some programmer dude, Commented May 30, 2020 at 1:43
If bit_len is not an integral multiple of 8, your malloc will come up short. You want to round up the number of bytes: uint8_t* hex_arr = malloc((bit_len + 7) / 8); — Craig Estey
– Craig Estey, Commented May 30, 2020 at 1:51

Mad Physicist · Accepted Answer · 2020-05-30 05:30:36Z

3

Strictly speaking, you don't need two loops, since the two arrays move in lock-step up to a factor of 8.

Your input array is as follows:

uint8_t bit_arr[] = {
    1, 0, 1, 1, 0, 1, 1, 1,
    1, 1, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 1, 1, 0};

The desired output is

uint8_t expected[] = {0xB7, 0xC0, 0x06}

Notice that the most significant bit comes first in this representation. Bits 0-8 in the array are the most to least significant bits in byte 0 of the output and so on.

This plays very well with how basic looping and bit-shifting works. You can push the bits one by one into the least significant bit of the output array:

uint8_t *hex_arr = malloc(bit_len / 8);
memset(hex_arr, 0, bit_len / 8);
for(int i = 0; i < bit_len; i++) {
    hex_arr[i / 8] <<= 1;
    hex_arr[i / 8] += bit_arr[i];
}

The moral of the story is that you must be careful as to how you define your representations and your data. Make sure that you understand where you want things to go conceptually, and you won't have a problem with either graphical or internal representations.

edited May 30, 2020 at 5:30

answered May 30, 2020 at 2:05

Mad Physicist

116k29 gold badges202 silver badges292 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mad Physicist Over a year ago

@DavidC.Rankin. For this application, it's irrelevant whether you have an array on the stack or a pointer to an array on the heap.

Mad Physicist Over a year ago

@DavidC.Rankin. I get no problem with the declaration, although it likely does something other than what I want. I've gone ahead and changed it as you suggest for completeness.

dbush · Accepted Answer · 2020-05-30 01:46:58Z

0

The value that you're shifting is where the problem in.

The first time you enter the inner loop, i is 0 and j is 0. This makes j-i 0 so the value in question gets OR'ed into the rightmost bit instead of the leftmost. Then when j is 1 your shift 1 so the bit goes into the second right bit instead of the second left.

So your shift is going from 0 to 7 when it should be going from 7 to 0. You fix this by subtracting the shift amount from 7.

hex_arr[index] |= bit_arr[j] << (7 - (j - i));

answered May 30, 2020 at 1:46

dbush

233k27 gold badges261 silver badges334 bronze badges

1 Comment

David C. Rankin Over a year ago

Or you could do a single loop and hex[i/8] |= (bit_arr[i] << (7 - (i % 8)));

lenik · Accepted Answer · 2020-05-30 02:28:19Z

0

You should change this:

for (i = 0; i < bit_len; i = j) {
    for (j = i; j < i + 8; ++j) {
      hex_arr[index] |= bit_arr[j] << (j - i);

into this:

for (i = 0; i < bit_len; i += 8) {
    for (j = 0; j < 8; ++j) {
      hex_arr[index] |= bit_arr[i+j] << (7 - j);

because your shifts reorder bits in the opposite direction.

edited May 30, 2020 at 2:28

answered May 30, 2020 at 1:46

lenik

23.6k4 gold badges38 silver badges44 bronze badges

1 Comment

Eric Postpischil Over a year ago

This breaks the loop on i since it uses j in i = j.

Collectives™ on Stack Overflow

Converting array of bits to array of hex in C through bitwise operations

3 Answers 3

2 Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related