0

I am writing a small C program to count the number of bits which need to be flipped to make one number equal to another.

The program works very fine but i observe abnormal behaviour (Program hangs) when i pass ULONG_MAX as an argument. Why is this happening? See code below

#include <stdio.h>
#include <limits.h>
#include <stddef.h>

/**
 * flip_bits - Count the number of bits to flip to equalize two numbers
 * @n: First number
 * @m: Second number
 *
 * Return: the number of bits to flip
 */
unsigned int flip_bits(unsigned long int n, unsigned long int m)
{
        unsigned long int diff, count;
        int i;

        diff = n ^ m;

        count = 0;
        i = 0;
        while (diff >> i)
        {
                if (diff >> i & 1)
                        count++;

                i++;
        }

        return (count);
}

/**
 * main - check the code
 *
 * Return: Always 0.
 */
int main(void)
{
    unsigned int n;

    n = flip_bits(1024, 1);
    printf("%u\n", n);
    n = flip_bits(402, 98);
    printf("%u\n", n);
    n = flip_bits(1024, 3);
    printf("%u\n", n);
    n = flip_bits(ULONG_MAX, 0);
    printf("%u\n", n);
    return (0);
}
Nwaburu Emeka Christian
  • 59
  • 5
  • Have you tried to use a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through your code to see what really happens? – Some programmer dude Oct 28 '22 at 10:52
  • 4
    `while (diff) { if (diff & 1) { count++; } diff >>= 1; }` – Weather Vane Oct 28 '22 at 10:56
  • 1
    The function is taking *ages* rather than hanging. How many loops does it take for `i++` to reach `diff` when `diff` is say `0xFFFFFFFFFFFFFFFF`? – Weather Vane Oct 28 '22 at 10:57
  • Thanks a lot @WeatherVane. This approach works. – Nwaburu Emeka Christian Oct 28 '22 at 11:01
  • 1
    @NwaburuEmekaChristian FYI, the problem with your code is it relies on being able to shift the entire value, leaving a zero result, but the C standard restricts the shift amount to one less than the number of bits in the integer type. So if you have a 64-bit int, the maximum shift amount is 63. But your original code won't terminate unless it's able to shift by 64. – Tom Karzes Oct 28 '22 at 11:05
  • 1
    @WeatherVane the issue is not that it's taking ages. The code would work as yours if we had infinite precision, after all `diff>>i` takes 64 cycles to exhaust the bits as **you don't have to count up to 2**64`. What happens is that `diff>>64` overflows and the cycle repeats from the beginning. – Fra93 Oct 28 '22 at 11:05
  • 1
    @TomKarzes, Thanks for clarifying this. I had placed a printf statement to within the while loop and noticed that it printed indefinitely. This explains the reason for the indefinite loop. So if my arguments where unsigned ints (16 bits), then the shift would be limited to 15 moves. Thanks – Nwaburu Emeka Christian Oct 28 '22 at 13:24

1 Answers1

0

Be explicit with signedness and size of all relevant types involved. Don't use bitwise arithmetic on signed numbers. You can simplify this whole code quite a bit by using a readable for loop instead:

#include <stdint.h>

uint32_t count_diff32 (uint32_t x, uint32_t y)
{
  uint32_t diff = x ^ y;
  uint32_t count = 0;
  for(size_t i=0; i<32; i++)
  {
    if (diff & (1u<<i))
    {
      count++;
    }
  }
  return count;
}
Lundin
  • 195,001
  • 40
  • 254
  • 396