Convert hexadecimal made up of 0's and 1's to binary equivalent

Question

I need a hexadecimal number converted to another one representing the binary value of it (not the actual value though).

For example, if I have 0x0101, I would like to get 0b0101, which means 0x5. The hexadecimal I get at the beginning is always composed of 0's and 1's.

It could also be a way to convert 0xf00f to 0b1001 (0xf's to 0b1's instead of 0x1's to 0b1's), which means 0x9. Actually, the hexadecimal number I have at the beginning is composed of f's and 0's, but it's easy to get the f's replaced by 1's by dividing it by 0xf. Example:

uint16_t bitMask = 0xf0f0;
uint16_t nybbleMask = 0;

//do some bit manipulation with bitMask
//get nybbleMask == 0xc (0b1010)

or:

bitMask = bitMask / 0xf;
//bitMask is now 0x1010

//do some bit manipulation with bitmask
//get nybbleMask == 0xc (0b1010)

Edit: I know I could easily do it with a loop, but I was wondering if I could do something equivalent with bitwise opetator. Also, I don't have access to math.h library.

score 2 · Answer 1 · edited Apr 25 '18 at 02:43

A one line fix for 16bit hex would be....

bin = ((hex%16)?1:0) + (((hex/16)%16)?2:0) + (((hex/256)%16)?4:0) + (((hex/4096)%16)?8:0);

though this is no the bitwise operations you want. Not sure if >> works on int or at least is specified to always work on uint16_t - You might want to look at this question to think about bitwise operators and uint16_t - if it is ok then

bin = (hex & 1) |
      (((hex >> 4) & 0x1) << 1) |
      (((hex >> 8) & 0x1) << 2) |
      (((hex >> 12) & 0x1) << 3);

would work given that your hex bytes are either F or 0.

Old answer for arbitrary size hex is below

int hex;
int bin;

int n, m, k;

//assume hex has your hex value
n=0; bin=0;
while(pow(16.0,(double)n)<(double)hex+0.5) // test if we are done
 {
  m=1; for(k=0;k<n;k++) m*=16; 
  if ((hex/m)%16!=0) {
     m=1;for(k=0;k<n;k++) m*=2;
     bin += m;
  }
  n++;
 }

this should convert any 0x.... into 0b.... where you get a 1 for each digit if the hex digit is not equal to zero. The key part is (hex/m)%16!=0 which tests the nth digit of the hex number to see if it is zero or non zero.

@JeremyPare - NB just edited with bitwise solution, but I would proceed with care for that..... glad it was helpful — tom, Apr 25 '18 at 02:27

Gene · Accepted Answer · 2018-04-26T04:09:08.690

This is pretty simple problem, which I assume is homework. @tom made it a bit harder than it needs to be.

You simply want to extract every 4th bit starting from the least significant, ignoring the 3 intervening zeros. I'll give you an algorithm. Writing the code shouldn't be hard:

let x be the hex coded binary number to convert
let val be the binary result value, initially zero
let n be the bit position we're currently finding, initially zero
while x is not zero
  let b be the least significant bit of x
  update val to be val or (b shifted left by n bits)
  increment n
  update x to be x shifted right by 4 bits

Here's another approach:

let val be 0
let hex_mask be 1
let bin_mask be 1
while hex_mask is not zero
  if (x and hex_mask) is non-zero, then update val to be val or bin_mask
  shift hex_mask left 4 bits
  shift bin_mask left 1 bit

Addition

Since you say it's not homework, let me show you that the second solution actually is a solution with only bitwise operators if you have a good compiler.

Here's code:

uint16_t hex_coded_binary_value(uint16_t x) {
  uint16_t val = 0;
  for (uint16_t h = 1, b = 1; h; h <<=4, b <<= 1)
    if (x & h) val |= b;
  return val;
}

If you compile this with a recent version of Apple clang, you'll get:

mov eax, edi
and eax, 1
mov ecx, edi
shr ecx, 3
and ecx, 2
or ecx, eax
mov eax, edi
shr eax, 6
and eax, 4
or eax, ecx
shr edi, 9
and edi, 8
lea eax, [rdi + rax]
ret

Note no loops! It's all shift, and, or, add, and move. gcc uses conditional move instructions, but also no loops.

What's the algorithm the compiler has discovered? If you were coding in C, it would look something like:

val = (x & 1)
    | ((x >> (4 - 1)) & (1 << 1))
    | ((x >> (8 - 2)) & (1 << 2))
    | ((x >> (12 - 3)) & (1 << 3));

This folds to

val = (x & 1) | ((x >> 3) & 2) | ((x >> 6) & 4) | ((x >> 9) & 8);

Note that the result has fewer operations than @tom's solution.

This also compiles to essentially the same as the original, but the C is longer and more error prone. The moral is to trust your compiler.

It is not for an homework but your algorithm works well. :) However I was more looking for a way to do this using only bitwise operators, the loop is pretty simple indeed. I clarified this in my OP. — Jeremy Pare, Apr 25 '18 at 01:56
@JeremyPare Please see the addition. Often, trying to beat the compiler is a bad idea. — Gene, Apr 26 '18 at 02:58

Convert hexadecimal made up of 0's and 1's to binary equivalent

2 Answers2