Simple way to find binary length of cpp_int

Question

What is a simplest way to find how many bits an arbitrary precision cpp_int is? For example 300 can be represented with a minimum of 9 bits.

I imagine an algorithm that repeatedly right shifts until the value reaches 0, I was wondering if there was a simpler solution.

possible duplicate of [What is the fastest way to calculate the number of bits needed to store a number](http://stackoverflow.com/questions/2721244/what-is-the-fastest-way-to-calculate-the-number-of-bits-needed-to-store-a-number) — Daniel Waechter, Aug 05 '14 at 07:06
You're basically asking for a fast integer base-2 log, which has a nice answer (not the accepted one though!) here: http://stackoverflow.com/questions/994593/how-to-do-an-integer-log2-in-c — Ben Hymers, Aug 05 '14 at 07:06

score 4 · Accepted Answer · answered Aug 05 '14 at 07:37

4

Boost has a built-in most significant bit operation, see for instance on this page

cpp_int i = 300;
unsigned int required_bits = msb(i);

answered Aug 05 '14 at 07:37

Stian Svedenborg

1,797
11
27

Chunde Huang · Answer 2 · 2014-08-05T07:51:50.503

0

void main()
{
    int n = 0;
    int v = 1;
    int cpp_int = 1003;//any value you like
    for (int i = 0; i < 31; i++)
    {
        if (v >= cpp_int)
        {
            break;
        }
        v <<= 1;
        n++;
    }
    printf("%d", n);
}

//this is for integer no larger that 32 bit representation.hope this helps

edited Aug 05 '14 at 07:51

answered Aug 05 '14 at 07:17

Chunde Huang

337
3
9

`cpp_int` is a (boost) type, not a variable name in the OP's mind. And `main` must return an `int`. And why use `printf` in C++ ?. And, it doesnt work... – quantdev Aug 05 '14 at 07:19
#include "stdio.h" void main() { int n = 1; cpp_int v = 1; int testValue = 1003;//any value you like for (int i = 0; i < sizeof(cpp_int）* 8; i++) { if (v >= testValue ) { break; } v <<= 1; n++; } printf("%d", n); } – Chunde Huang Aug 05 '14 at 07:27
printf is used to print the value 'n'. you need to include other header file of boost C++ if necessary. this is just algorithm. I　tested on my computer, if you change cpp_int to standard type int, it works well. – Chunde Huang Aug 05 '14 at 07:28
The binary of '1003' is '1111101011' having 10 bits. – Ali Mohyudin Aug 05 '14 at 07:40
Sorry, I realize that 'n' should be set to zero at beginning, so you can get the right answer. – Chunde Huang Aug 05 '14 at 07:53

score 0 · Answer 3 · answered Aug 05 '14 at 07:33

0

I post the image so you can see how it works in standard c++. it's not hard to translate to boost C++, the idea is exactly the same.

answered Aug 05 '14 at 07:33

Chunde Huang

337
3
9

score 0 · Answer 4 · answered Aug 05 '14 at 07:37

I figure out this method that gives you the number of maximum bits that a number can use. Try this line in your code:

int ans = log2(cpp_int)+1;

The number of bits needed to represent an integer n is given by rounding down log2(n) and then adding 1 to it.

In general log2(n) gives the power of 2 which is required to get 'n'. If you've read anything about binary numbers you can easily understand why we're using log with base 2.

For the above line to work you've to include 'math.h' header file as:

#include <math.h>

Simple way to find binary length of cpp_int

4 Answers4