Counting the binary representation of an Integer

Question

I have to count the length of binary representation of an integer. I've tried something like this:

int binaryLength(int n)
{
      int i = 32;
      while (i > 0)
      {
           if (n >> i & 1) break;
           else i--;
       }
       return i;
 }

But when i have number like 9 (1001), this function returns me 32.

you can't shift a 32 bit integer by 32. AFAIK that's undefined behaviour, but usually it behaves like a shift modulo 32, i.e. you effectively shift by 0. As your number (9) has the least significant bit set, your loop breaks on the first iteration. Try starting at 31. — Karsten Koop, Nov 28 '16 at 12:08
@Lundin: 1) No magic numbers. That's what `CHAR_BIT` is for. 2) `int` may use not all bits. — too honest for this site, Nov 28 '16 at 12:15
For negative values, it is implementation defined. And for `int` with less than **33** bits, it is undefined behaviour. — too honest for this site, Nov 28 '16 at 12:16
oops this is more correct [What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C](http://stackoverflow.com/q/671815/995714) — phuclv, Nov 28 '16 at 13:02
@Olaf 1) CHAR_BIT might not be 8. So the raw number 8 is better for the purpose of self-documenting code. "Programmers" that don't understand that one byte contains 8 bits better not be reading C code. 2) The question asks for the binary representation. `int` will certainly use all bits (though there may be padding bits on wildly exotic, mostly fictional systems). — Lundin, Nov 28 '16 at 14:01
@Lundin: "I have to count the length of binary representation of an integer" - So OP wants all bits, which would not work with your proposed code if a byte has more than 8 bits (you avoid the problem with `int` having 16 bits, though). And not sure what you mean with _"Programmers" that don't understand that one byte contains 8 bits better not be reading C code_. I do understand on **most** machines it has 8 bits. But [this question](http://stackoverflow.com/questions/40843225/integer-and-boolean-types-to-use-in-an-embedded-system-with-two-architectures) shows one should not rely without need. — too honest for this site, Nov 28 '16 at 18:29
@Olaf People who try to write C so it is portable to wildly exotic DSPs are just misguided and wasting everyone's time by whining about such systems. Most of DSP software is still written in assembler. In particular, wildly exotic DSPs or non-two's complement computers are completely irrelevant considerations for beginner programmers. — Lundin, Nov 29 '16 at 08:10

Bathsheba · Accepted Answer · 2016-11-28T12:45:07.670

2

I'd abandon the loop approach if I were you.

Here's the fastest way I know of - coded specifically for a 32 bit int. It will not work for a negative integer (the bit patterns for negative integers are platform dependent anyway). Add an extra line for a 64 bit int; the scheme ought to be obvious.

int binaryLength(int n)
{
    int i = 0; // the minimum number of bits required.
    if (n >= 0x7FFF) {n >>= 16; i += 16;}
    if (n >= 0x7F) {n >>= 8; i += 8;}
    if (n >= 0x7) {n >>= 4; i += 4;}
    if (n >= 0x3) {n >>= 2; i += 2;}
    if (n >= 0x1) {n >>= 1; i += 1;}
    return i;
}

edited Nov 28 '16 at 12:45

answered Nov 28 '16 at 12:17

Bathsheba

231,907
34
361
483

1

This really doesn't work for negative numbers, so I don't see why it takes an `int` (especially with that comment about right-shifting, which of course is way worse for signed numbers). – unwind Nov 28 '16 at 12:41
1

@unwind: Mainly it's because that's the way the OP has it. There's a movement amongst the cool cats to not use `unsigned`, and constrain the signed at the point of use. So I didn't want to mess about with the type. – Bathsheba Nov 28 '16 at 12:42
If you disallow negative values, you can very well use unsigned types. They allow to pass signed integers with positive values as well, so nothing changes. Not suer what you mean with "cool cats", but in general when shifting arbitrary values, good programmers prefer unsigned integers. That may differ in other languages where encoding and operations are well defined. – too honest for this site Nov 29 '16 at 09:53

score 0 · Answer 2 · answered Nov 28 '16 at 12:15

0

You can find the length by doing the following:

length = ceil(log(N + 1)/log(2));

that is the length is the ceiling of the log base 2 of N. Since I can't remember the log base 2 function name, I am doing the equivalent above. You need to N + 1 to correctly account for N being a direct power of 2 and thus needing the one extra bit to represent it. Example N = 8 = 1000 in binary. log base 2 of 8 is 3 and the ceiling of 3 is 3, but log base 2 of 9 is 3.16993 and the ceiling of 3.16993 is 4

answered Nov 28 '16 at 12:15

Sohil Omer

1,171
7
14

2

The problem with this method is that `log` can underestimate the result. That floating point imprecision is enough for the result to "go off". – Bathsheba Nov 28 '16 at 12:18
moreover `log` is also inefficient. There are tons of efficient ways to count bits and new CPUs even have hardware support for it – phuclv Nov 28 '16 at 12:59

score 0 · Answer 3 · answered Nov 28 '16 at 12:19

0

Firstly, consider using unsigned int - I suspect that's what you want anyway. Then a sensible approach would be to keep shifting your input number down until it is zero. Something like:

unsigned int binaryLength(unsigned int n)
{
      unsigned int i = 0;
      while (n >>= 1)
      {
         ++i;
      }

      return i;
}

There are much faster ways (you can simply use a look-up table etc) but this seems close to your original approach.

answered Nov 28 '16 at 12:19

Sam Holloway

1,999
15
14

1

@Bathsheba I do not see why, but the function is off by 1: http://ideone.com/LyasYm – mch Nov 28 '16 at 12:36
1

`n >>= 1` evaluates to the "newly shifted" value, if you get my meaning. So you skip over one `++i`. My UB comment is hogwash by the way, as you're shifting "one by one". – Bathsheba Nov 28 '16 at 12:37
A negative int would return 32 as the first bit (sign bit) is a 1. Would that first need to be made positive? (e.g. `if ((int)n<0) n -=n;`) – Paul Ogilvie Nov 28 '16 at 13:00

MayurK · Answer 4 · 2016-11-28T13:20:00.657

0

From wikipedia,

An N-bit two's-complement numeral system can represent every integer in the range −(2N − 1) to +(2N − 1 − 1)...

This should work for both negative and positive numbers.

int binaryLength(int n)
{
    int num       = n;
    int nMinus1   = 0;
    int i         = 0;

    if(0 > num)
        num = -num;

    if(0 >= n)
    {
        while(((1<<nMinus1)-1) <= num)
        {
            nMinus1++;
        }
    } else {
        while((1<<nMinus1) <= num)
        {
            nMinus1++;
        }
    }

    i = nMinus1+1;

    printf("Number %d binary length %d\n", n, i);

    return 0;
}

Tested with some inputs:

Number 0 binary length 2                                                                                                                                            
Number 1 binary length 2                                                                                                                                            
Number -1 binary length 3                                                                                                                                           
Number 9 binary length 5                                                                                                                                            
Number -9 binary length 5

edited Nov 28 '16 at 13:20

answered Nov 28 '16 at 13:08

MayurK

1,925
14
27

why so complex? – phuclv Nov 28 '16 at 13:09
@LưuVĩnhPhúc: Sorry I didn't get. I wanted to take care of both positive and negative numbers. – MayurK Nov 28 '16 at 13:20
no need for that. there are much more efficient ways http://stackoverflow.com/q/671815/995714 https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious http://stackoverflow.com/q/9041837/995714 – phuclv Nov 28 '16 at 13:35
Oh yes. But I was thinking differently. If number is -1, then it will be stored as 0xFFFFFFFF in 32-bit integer. But actually you can write it in two bits as 11, assume one for sign and one for value. I thought the question is to find minimum number of bits required to store number. – MayurK Nov 28 '16 at 13:49
1

I don't think so, it's about "binary representation" in memory. Minimum bits to represent negative numbers would be another problem, and it depends on what format is used for signed number – phuclv Nov 28 '16 at 13:54

Counting the binary representation of an Integer

4 Answers4