C bit counting causes unexpected behaviour

Question

I was writing a Hamming weight function in C. I wanted to know if I did it correctly, so my plan was to test on the number 5. I didn't want to google the binary for 5 and wrote some code to do it myself, however when I ran the code I got this:

testing code
bit length of 5: 32

five: -1354390872 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

This didn't make sense as nothing should be able to output such a large negative number. Here's my code

#include <stdio.h>

int main() {
      printf("\ntesting code\n");
      int fv[32];
      int fiv = 5;
      for (int i = 0; i < 32; i++) {
            if (fiv & 1) fv[32 - i] = 1; else fv[32 - i] = 0;
            fiv >>= 1;
      }
      printf("bit length of 5: %ld\n\n", (sizeof(5) * 8));
      printf("five: ");
      for (int i = 0; i < 32; i++) {
            printf("%d ", fv[i]);
      }
      printf("\n");
      return 0;
}

I was expecting to populate the array with integers 0 or 1 where the array would represent the binary value of the number. It certainly populated the array with 32 bit integers representing the number, however -1354390872 is not 0, nor 1. I've tried changing the number I iterate through to be (sizeof(n) * 8 to account for the size of a byte, however that just hangs and I couldn't figure it out as there is no manpage for sizeof(). I also tried replacing the line where I set fv[32 - i] to this unoptimised mess: if (fiv & 1) fv[32 - i] = 1; else fv[32 - i] = 0; in hopes that it would change the output

Can someone help, I'm sure there's a binary format that I don't know about that I could be using, but I honestly don't know it.

Edit: Running the code multiple times gives completely random outputs of very large numbers. Example:

testing code
bit length of 5: 32

five: -956652888 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
forward:~/cproblem/declareyourvariablesc $ ./main

testing code
bit length of 5: 32

five: -754855256 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
forward:~/cproblem/declareyourvariablesc $ ./main

testing code
bit length of 5: 32

five: 104133288 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
forward:~/cproblem/declareyourvariablesc $ ./main

testing code
bit length of 5: 32

five: -1662766424 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
forward:~/cproblem/declareyourvariablesc $ ./main

testing code
bit length of 5: 32

five: -103538008 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
forward:~/cproblem/declareyourvariablesc $ ./main

testing code
bit length of 5: 32

five: 1071841960 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

fv[32 - i] is out-of-bounds when i is zero hence undefined behaviour. — G.M.
– G.M., Commented Dec 4, 2023 at 15:47
thank you! forgot that I can do i = 32; i > 0; i-- instead — synnøve
– synnøve, Commented Dec 4, 2023 at 15:50
You don't have to store the bits in an array for the hamming weight. You could just increment a counter. There are much faster ways also you can find easily here on SO. — Simon Goater
– Simon Goater, Commented Dec 4, 2023 at 15:52
When doing bit operations, it is better to use unsigned ints to avoid problems with the sign bit. — stark
– stark, Commented Dec 4, 2023 at 16:17
@synnøve You won't find a manpage for sizeof since it's an operator, not a library function. — Paul Lynch
– Paul Lynch, Commented Dec 4, 2023 at 17:54

chux · Accepted Answer · 2023-12-04 17:29:51Z

4

@chqrlie already answered the correct solution.

Just to explain what is happening here: Since fv is defined locally in the main function and is not set to zero, its values are undefined. Your for loop iterates from 0 to 31 so you are changing the values of fv at position 32 to 1. Position 32 is out of range and results in undefined behavior.

But in particular the position 0 was never written keeping its "random" value.

edited Dec 4, 2023 at 17:29

chux

158k17 gold badges160 silver badges311 bronze badges

answered Dec 4, 2023 at 16:34

nick

412 bronze badges

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

Comments

chqrlie · Accepted Answer · 2023-12-04 19:28:22Z

4

Instead of fv[32 - i], you should use fv[32 - 1 - i] to avoid accessing beyond the end of the array. As posted, the code has undefined behavior, which explains the observed output, but anything else could happen too.

To void these computations, you can use a down loop (note the use of the postdecrement operator in i--):

      for (int i = 32; i-- > 0;) {
          if (fiv & 1)
              fv[i] = 1;
          else
              fv[i] = 0;
          fiv >>= 1;
      }

And you can simplify the loop body:

      for (int i = 32; i-- > 0;) {
          fv[i] = fiv & 1;
          fiv >>= 1;
      }

Also note that sizeof(5) is the size in byte of type int and has type size_t which may be different from unsigned long. size_t requires the conversion %zu for printf. To avoid compatibility issues on legacy systems, I recommend casting the size_t expression as (unsigned) and using %u. Also note that * 8 assume 8-bit bytes, which are quite ubiquitous today, except for some DSPs and ancient CPUs. Purists would use CHAR_BIT defined in <limits.h>.

Here is the modified code:

#include <stdio.h>

int main(void) {
    printf("\ntesting code\n");

    int fv[32];
    int fiv = 5;

    for (int i = 32; i-- > 0;) {
        fv[i] = fiv & 1;
        fiv >>= 1;
    }
    printf("bit length of 5: %u\n\n", (unsigned)(sizeof(5) * 8));
    printf("five: ");
    for (int i = 0; i < 32; i++) {
        printf("%d ", fv[i]);
    }
    printf("\n");
    return 0;
}

edited Dec 4, 2023 at 19:28

answered Dec 4, 2023 at 15:52

chqrlie

152k12 gold badges145 silver badges231 bronze badges

2 Comments

synnøve Over a year ago

thanks! now a different issue happens where it doesn't output anything, progress!: testing code bit length of 5: 32 five:

chqrlie Over a year ago

@synnøve: you might have broken something... try the code from my answer.

Collectives™ on Stack Overflow

C bit counting causes unexpected behaviour

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related