3

I am trying to reverse the bits of an integer in the C program. Even though I have looked at the same question by another user, I was unable to understand most of the code that was written. I have noticed that the code I have is similar to the answer by Eregrith but I cannot identify the problem with my code below:

#include <stdio.h>
#include <stdlib.h>

unsigned int reverse_bits(unsigned int num)
{
unsigned int reverse_num = 0; /* initialize the result*/
unsigned int count = sizeof(unsigned int) * 8 - 1; /* counter to track the number of bits in the integer*/

while (num != 0)
{
    unsigned int last_bit = num & 1; /* get the right-most bit*/
    reverse_num = reverse_num | last_bit; /* add that bit to the right-most bit of the desired reversed bits*/
    reverse_num = reverse_num << 1; /* shift the reversed bits left*/
    num = num >> 1; /* shift the original bits right*/
    count--;
}
reverse_num = reverse_num << count; /* If the original bits have only 0
s then shift the remaining bits left*/

return reverse_num;
}

int main()
{

reverse_bits(1);
}

If I enter reverse_bits(1), the code returns -2147483648, which clearly did not reverse the bits of the integer 1. I am new to code and I am having difficulty locating the source of this error. Without having to change the entire code, how can I modify my existing code to return the correct output?

5
  • There is a difference between integer and unsigned integer. Also, if you use printf() to print your result, you want to use %d for integer and %u for unsigned integer.
    – SSC
    Commented Aug 1, 2017 at 4:12
  • How did you see that -2147483648 that you are mentioning? You are using unsigned int, you shouldn't see any negative number, unless you are mixing int and unsigned int by mistake, which I don't see anywhere in your code.
    – m0h4mm4d
    Commented Aug 1, 2017 at 4:13
  • 2
    How do you conclude the result was -2147483648 ? All your code does is invoke the reverse_bits function. Where is the code that generated your output on which you base your conclusion?
    – WhozCraig
    Commented Aug 1, 2017 at 4:14
  • "which is clearly did not reverse the bits of the integer 1". If you don't like what you get, you should always tell us what you expect to get and why.
    – Gerhardh
    Commented Aug 1, 2017 at 6:17
  • 1
    Where does the magic constant 8 come from? Did you mean CHAR_BIT? Commented Aug 1, 2017 at 8:07

2 Answers 2

2

Although you didn't provide the part of code that does the printing, it is somehow obvious that you are mixing int and unsigned int.

For printf() function family the specifier for unsigned int is %u so if you want to print your output, you should use:

printf("%u\n", reverse_bits(1));

Other than that your code is OK and besides, note that if a machine uses 2's complement and 32 bits for an int, -2147483648 = 10000000000000000000000000000000 which is a bit reversal of 1 = 00000000000000000000000000000001.

3
  • 1. By mixing int and unsigned int, do you mean that I am using unsigned int when I should be using int? 2. So, after replacing reverse_bits(1); with printf("%u\n", reverse_bits(1));, I receive 2147483648 Process returned 11 (0xB) So, the negative sign changed to a positive sign, but it says the process returned 11, which I find strange. 3. Is there any way for me to request that the machine print out 10000000000000000000000000000000 instead of -2147483648?
    – J.S.
    Commented Aug 1, 2017 at 4:34
  • put %X instead of %u in printf. you will get better clarity. printf("%X\n", reverse_bits(1)); Commented Aug 1, 2017 at 5:47
  • 1
    1. You should be using unsigned int. I was referring to the way you get your output. How did you get the output before I suggest to add printf()? 2. That's possibly because your main() function doesn't return anything. Add return 0; to the end of main. And yes, a bit reversal of 1 should return 2 ^ 31 = 2147483648. 3. write a function to convert from decimal to binary. That is trivial. If you are developing under Win32/Win64, MS provides a non-standard function itoa() that can do that for you but I recommend against using it.
    – m0h4mm4d
    Commented Aug 1, 2017 at 6:04
2

How do you observed that it returns a negative value? unsigned ints only are used in your code... I supposed that you tried to print the returned value as an int with %d, but that is undefined behavior. To print an unsigned you must use %u or %x.

But your reversal is wrong. You shift the result after adding the last bit, which should be the converse. You also miss the count of bits in an unsigned int (less by one). The following should work:

#include <stdio.h>
#include <stdlib.h>

unsigned int reverse_bits(unsigned int num) {
  unsigned int reverse_num = 0; /* initialize the result*/
  unsigned int count = sizeof(unsigned int) * 8; /* counter to track the number of bits in the integer*/

  while (num != 0) {
      unsigned int last_bit = num & 1; /* get the right-most bit*/
      reverse_num <<= 1; /* add one place for the next bit */
      reverse_num |= last_bit; /* add that bit to the right-most bit of the desired reversed bits*/
      num >>= 1; /* remove one bit from the original */
      count--;
    }
  reverse_num <<= count; /* If the original bits have only 0 s then shift the remaining bits left*/
  return reverse_num;
}

int main() {
  printf("%08x\n",reverse_bits(1));
  printf("%08x\n",reverse_bits(3));
  printf("%08x\n",reverse_bits(0x0F0FFFFF));
}

---- EDIT ----

As comments mentioned the possible? UB in the case of num begin null, I suggest to add a test to eliminate that problem:

  if (count!=sizeof(reverse_num)) {
      reverse_num <<= count; /* If the original bits have only 0 s then shift the remaining bits left*/
  } else {
      reverse_num = 0;
  }
  return reverse_num;
11
  • 2
    With an input of 0, you do reverse_num <<= sizeof(unsigned int) * 8 which is undefined behavior. Commented Aug 1, 2017 at 7:28
  • @PaulHankin Wrong, 6.5.7 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 × 2^E2, reduced modulo one more than the maximum value representable in the result type. Commented Aug 1, 2017 at 7:30
  • 1
    You have to read to the end of the standard to J.2, and look at the list of undefined behaviors. One bullet is: "An expression is shifted by a negative number or by an amount greater than or equal to the width of the promoted expression (6.5.7)". Here, sizeof(unsigned int)*8 is the width of the promoted expression (assuming 8 bit bytes), so the shift is undefined behavior. Commented Aug 1, 2017 at 7:42
  • @PaulHankin is right. You are relying on undefined behavior for the case of 0. Because that requires a left shift equal to bit width of int which is undefined behavior but then again for 0 you can just return without doing anything.
    – m0h4mm4d
    Commented Aug 1, 2017 at 8:05
  • 1
    Isn't that new piece of code too much? I'd say just if(num == 0) return 0; at the top of function is better.
    – m0h4mm4d
    Commented Aug 1, 2017 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.