Number of digits in the binary representation of an integer

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

I usually find the number of digit in the binary representation of an integer in the following way:

int digit = 1 + (int)log2(n);

I used to think that this way is absolutely correct as I never found any error. But today I got WA in problem number B (Codeforces Round 456) due to finding the number of digits in this way and I understood that this way isn't 100% correct. An integer n = 288230376151711743 was given in the case in which I got WA verdict.

While testing the error, I printed the 2 base log of 288230376151711743 using the log2() function of C++ and it printed 58. According to that 2^58 should be equal to 288230376151711743, but it isn't. 2^58 is equal to 288230376151711744.

So I guess, the value of log2(288230376151711743) is 57.99999999... or something like that which is very close to 58 and due to precision issues log2() function returns 58 in this case.

To avoid such errors I changed the way of finding the number of digits in binary in the following way:

int digit = 1 + (int)log2(n);
long long int x=(long long int)pow(2,d-1);
if(x>n) d--;

After changing my code in this way I got AC verdict, but I am still not sure about the accuracy of my way.

I want to know how much accurate is this way of finding the number of digits. If it is still not accurate, kindly suggest some other ways of finding the number of digits in the binary form of an integer which are accurate and efficient enough.

long long power(long long a, long long n) { if (n == 0) return 1; long long t = power(a, n / 2); if (n % 2 == 0) return t * t; else return t * t * a; } long long logarit(long long n) { long long x = 62; while (power(2, x) > n) x --; return x; }

Комментарии (21)

Показать архивные | Написать комментарий?

Medo.

6 лет назад, # |

+11

log2/pow and these functions use doubles so precision might be bad. Don't use them in these cases.

If you want to know how many 1's are number in base 2, then just iterate on each bit individually, and check if it's 1.

For example for (int i = 0 ; i < 62 ; ++i ) if((number) & (1LL << i)) ++ones;

→ Ответить

ankeet

6 лет назад, # ^ |

← Rev. 3 →

For counting ones, it might be faster to use the "fenwick tree" method where you remove the lowest set bit each time:

int ones = 0;
while(x){
    x -= x & - x;
    ++ones;
}

I ran a quick test comparing the two methods, and it seems as though fenwick runs faster on a large number of random test cases:

code

#include <bits/stdc++.h>
typedef long long ll;    
typedef long double ld;  
#define pb push_back     
using namespace std;


int f1(ll x){
    int ones = 0;
    while(x){
        x -= x & - x;
        ++ones;
    }
    return ones;
}

int f2(ll x){
    int ones = 0;
    for(int i = 0; i < 62; ++i){
        if(x & (1ll << i)) ++ones;
    }
    return ones;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll a = clock();
    for(int i = 0; i < 1000; i++) f1(1ll*rand()*rand());
    ll b = clock();
    for(int i = 0; i < 1000; i++) f2(1ll*rand()*rand());
    ll c = clock();
    
    cout << (b - a) << endl;
    cout << (c - b) << endl;
    return 0;    
}

Edit: __builtin_popcountll(x) is faster than either of the two methods, so use that instead.

BumbleBee

Can this way give any error?

makarfi

I also had thesame error in java with the following code

long num = 1L << (int) Math.ceil(Math.log(n)/ Math.log(2));
if (num > n) num >>= 1;

rahulkhairwar

In Java, you can simply use

int len = Integer.toBinaryString(x).length();

dalex

Integer.numberOfTrailingZeroes(Integer.highestOneBit(x)) + 1

dacin21

+13

With gcc you can compute $\text{[math]}$ using

__builtin_clzll(1ll) - __builtin_clzll(n)

which should get compiled to use the bsrinstruction, so it's really fast.

Does it give the accurate value of log2(288230376151711743)?

The argument gets passed as an unsigned long long, so no precision is lost and the answer will be correct for any positive 64-bit integer. (n=0 is UB or unspecified as far as I remember.)

PS: To compute the number of ones in the base 2 representation, use

__builtin_popcountll(n)

It works, thanks.

motatoes

← Rev. 2 →

The main problem is not about speed its about precision, As the OP stated

lg(288230376151711743) is slightly smaller than 58,

lg(288230376151711743+1) is exactly 58.

The result of the first after floor should be 57, but due to precision its returned as 58.

farmersrice

__builtin_clzll works with integer type, there's no precision error

oToToT

Also, you could use std::__lg(n) for cleaner code.

taxi_driver

I usually use

Time complexity : O(log n)

while(n>0)
 {
    n/=2;
    cnt++;
 }

cnt is the number of bits

Anachor

A GCC specific solution is to use __builtin_clz() function. It gives you the number of leading zeroes in the binary representation of a number. So, if you subtract it from 32 (number of bits in an int), you get what you want. For long long, you need to use 64 — __builtin_clzll().

Thanks. It works. What is the complexity?

Yash_

It's complexity is O(log N), same as that of log2(), but if you check the implementation, the number of cycles __builtin_clzll() takes is much lesser. I just ran them both for 10^8 numbers. log2() took 2.6 seconds while __builtin_clzll() took 0.4 seconds.

Moreover, __builtin_clzll() returns an int so you won't have any precision issues

Yes. I tested it too. I ran both functions on a vector of 10^6 long long integers. __builtin_clzll() was more efficient.

quanpham0805

When I started learning algorithm (5 months ago), I was lazy that time and keep searching for functions that help me to do things faster (such as pow and log) but one day, I got some bugs with the function pow and log, the result could not be exactly, so I decided to use my own. Here is the code that I'm using, with the function logarit, you can modify it tho, the function power runs in fast time ( O(log)).

Aaronus23

I had the exact same problem, and I solved it casting the parameter as a long double

like so

int digit = 1 + (int)log2((long double)n)

I tried with this and it is still not accurate. It is still showing 58 when I print this:

(int)log2((long double)288230376151711743)

Блог пользователя BumbleBee