How to do an integer log2() in C++?
You can use this method instead:
int targetlevel = 0;
while (index >>= 1) ++targetlevel;
Note: this will modify index. If you need it unchanged, create another temporary int.
The corner case is when index is 0. You probably should check it separately and throw an exception or return an error if index == 0.
How to write log base(2) in c/c++
Simple math:
log2 (x) = logy (x) / logy (2)
where y can be anything, which for standard log functions is either 10 or e.
Fast computing of log2 for 64-bit integers
Intrinsic functions are really fast, but still are insufficient for a truly cross-platform, compiler-independent implementation of log2. So in case anyone is interested, here is the fastest, branch-free, CPU-abstract DeBruijn-like algorithm I've come to while researching the topic on my own.
const int tab64[64] = {
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5};
int log2_64 (uint64_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value |= value >> 32;
return tab64[((uint64_t)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58];
}
The part of rounding down to the next lower power of 2 was taken from Power-of-2 Boundaries and the part of getting the number of trailing zeros was taken from BitScan (the (bb & -bb) code there is to single out the rightmost bit that is set to 1, which is not needed after we've rounded the value down to the next power of 2).
And the 32-bit implementation, by the way, is
const int tab32[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31};
int log2_32 (uint32_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}
As with any other computational method, log2 requires the input value to be greater than zero.
What's the quickest way to compute log2 of an integer in C#?
The Cleanest and Quickest... (works in .Net core 3.1 and up and takes the performance lead starting in .Net 5.0)
int val = BitOperations.Log2(x);
Runner up... (fastest in versions below .Net 5, 2nd place in .Net 5)
int val = (int)((BitConverter.DoubleToInt64Bits(x) >> 52) + 1) & 0xFF;
Notes:
- The idea of using the exponent in a floating-point was inspired by SPWorley
3/22/2009. - This also supports more than 32 bits. I have not tested the max but did go to at least 2^38.
- Use with caution on production code since this can possibly fail on architectures that are not little-endianness.
Here are some benchmarks: (code here: https://github.com/SunsetQuest/Fast-Integer-Log2)
1-2^32 32-Bit Zero
Function Time1 Time2 Time3 Time4 Time5 Errors Support Support
Log2_SunsetQuest3 18 18 79167 19 18 255 N N
Log2_SunsetQuest4 18 18 86976 19 18 0 Y N
LeadingZeroCountSunsetq - - - 30 20 0 Y Y
Log2_SPWorley 18 18 90976 32 18 4096 N Y
MostSigBit_spender 20 19 86083 89 87 0 Y Y
Log2_HarrySvensson 26 29 93592 34 31 0 Y Y
Log2_WiegleyJ 27 23 95347 38 32 0 Y N
Leading0Count_phuclv - - - 33 20 10M N N
Log2_SunsetQuest1 31 28 78385 39 30 0 Y Y
HighestBitUnrolled_Kaz 33 33 284112 35 38 2.5M N Y
Log2_Flynn1179 58 52 96381 48 53 0 Y Y
BitOperationsLog2Sunsetq - - - 49 15 0 Y Y
GetMsb_user3177100 58 53 100932 60 59 0 Y Y
Log2_Papayaved 125 60 119161 90 82 0 Y Y
FloorLog2_SN17 102 43 121708 97 92 0 Y Y
Log2_DanielSig 28 24 960357 102 105 2M N Y
FloorLog2_Matthew_Watso 29 25 94222 104 102 0 Y Y
Log2_SunsetQuest2 118 140 163483 184 159 0 Y Y
Msb_version 136 118 1631797 212 207 0 Y Y
Log2_SunsetQuest0 206 202 128695 212 205 0 Y Y
BitScanReverse2 228 240 1132340 215 199 2M N Y
Log2floor_version 89 101 2 x 10^7 263 186 0 Y Y
UsingStrings_version 2346 1494 2 x 10^7 2079 2122 0 Y Y
Zero_Support = Supports Zero if the result is 0 or less
Full-32-Bit = Supports full 32-bit (some just support 31 bits)
Time1 = benchmark for sizes up to 32-bit (same number tried for each size)
Time2 = benchmark for sizes up to 16-bit (for measuring perf on small numbers)
Time3 = time to run entire 1-2^32 in sequence using Parallel.For. Most results range will on the larger end like 30/31 log2 results. (note: because random was not used some compiler optimization might have been applied so this result might not be accurate)
Time4 = .Net Core 3.1
Time5 = .Net 5
Benchmark notes: AMD Ryzen CPU, Release mode, no-debugger attached, .net core 3.1
I really like the one created by spender in another post. This one does not have the potential architecture issue and it also supports Zero while maintaining almost the same performance as the float method from SPWorley.
Update 3/13/2020: Steve noticed that there were some errors in Log2_SunsetQuest3 that were missed.
Update 4/26/2020: Added new .Net Core 3's BitOperations.LeadingZeroCount() as pointed out by phuclv.
log2 of an integer that is a power of 2
You can just count the number of leading or trailing zero bits, because any exact power-of-two is represented as a single 1 bit, with all other bits 0. Many CPUs have special instructions for doing this, and compilers such as gcc have intrinsics for these operations, which get compiled to a single instruction on appropriate architectures.
If you have an efficient clz ("count leading zeroes") then a log2 implementation might look like this:
int32_t ilog2(uint32_t x)
{
return sizeof(uint32_t) * CHAR_BIT - clz(x) - 1;
}
(Note: returns -1 for ilog2(0).)
When using gcc or a gcc-compatible compiler you can just define clz like this:
#define clz(x) __builtin_clz(x)
Microsoft has something similar: BitScanReverse.
Note that it might appear more convenient to count trailing zeroes (using a ctz instruction), but a clz instruction is more widely available on different CPU architectures.
A further bonus of using clz rather than ctz is that you get floor(log2(x)) for non-power-of-2 values, making your ilog2 function more generally useful than if you had used ctz, which only works for exact powers-of-2.
See also: Finding the first set bit in a binary number.
Compute fast log base 2 ceiling
This algorithm has already been posted, but the following implementation is very compact and should optimize into branch-free code.
int ceil_log2(unsigned long long x)
{
static const unsigned long long t[6] = {
0xFFFFFFFF00000000ull,
0x00000000FFFF0000ull,
0x000000000000FF00ull,
0x00000000000000F0ull,
0x000000000000000Cull,
0x0000000000000002ull
};
int y = (((x & (x - 1)) == 0) ? 0 : 1);
int j = 32;
int i;
for (i = 0; i < 6; i++) {
int k = (((x & t[i]) == 0) ? 0 : j);
y += k;
x >>= k;
j >>= 1;
}
return y;
}
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
printf("%d\n", ceil_log2(atol(argv[1])));
return 0;
}
quickly find the integer part of the base 2 logarithm
The standard library function frexp does exactly that: it decomposes a double into an integer exponent and a normalized mantissa.
If you are content with the floor of the logarithm, rather than rounding the logarithm to the nearest integer, you are probably better off with the newer standard library function ilogb.
Note that these two functions treat zeros and infinities differently, so they are not quite interchangeable.
How to calculate the log2 of integer in C as precisely as possible with bitwise operations
You will base an algorithm on the formula
log2(x/y) = K*(-log(x/y));
where
K = -1.0/log(2.0); // you can precompute this constant before run-time
a = (y-x)/y;
-log(x/y) = a + a^2/2 + a^3/3 + a^4/4 + a^5/5 + ...
If you write the loop correctly—or, if you prefer, unroll the loop to code the same sequence of operations looplessly—then you can handle everything in integer operations:
(y^N*(1*2*3*4*5*...*N)) * (-log(x/y))
= y^(N-1)*(2*3*4*5*...*N)*(y-x) + y^(N-2)*(1*3*4*5*...*N)*(y-x)^2 + ...
Of course, ^, the power operator, binding tighter than *, is not a C operator, but you can implement that efficiently in the context of your (perhaps unrolled) loop as a running product.
The N is an integer large enough to afford desired precision but not so large that it overruns the number of bits you have available. If unsure, then try N = 6 for instance. Regarding K, you might object that that is a floating-point number, but this is not a problem for you because you are going to precompute K, storing it as a ratio of integers.
SAMPLE CODE
This is a toy code but it works for small values of x and y such as 5 and 7, thus sufficing to prove the concept. In the toy code, larger values can silently overflow the default 64-bit registers. More work would be needed to make the code robust.
#include <stddef.h>
#include <stdlib.h>
// Your program will not need the below headers, which are here
// included only for comparison and demonstration.
#include <math.h>
#include <stdio.h>
const size_t N = 6;
const long long Ky = 1 << 10; // denominator of K
// Your code should define a precomputed value for Kx here.
int main(const int argc, const char *const *const argv)
{
// Your program won't include the following library calls but this
// does not matter. You can instead precompute the value of Kx and
// hard-code its value above with Ky.
const long long Kx = lrintl((-1.0/log(2.0))*Ky); // numerator of K
printf("K == %lld/%lld\n", Kx, Ky);
if (argc != 3) exit(1);
// Read x and y from the command line.
const long long x0 = atoll(argv[1]);
const long long y = atoll(argv[2]);
printf("x/y == %lld/%lld\n", x0, y);
if (x0 <= 0 || y <= 0 || x0 > y) exit(1);
// If 2*x <= y, then, to improve accuracy, double x repeatedly
// until 2*x > y. Each doubling offsets the log2 by 1. The offset
// is to be recovered later.
long long x = x0;
int integral_part_of_log2 = 0;
while (1) {
const long long trial_x = x << 1;
if (trial_x > y) break;
x = trial_x;
--integral_part_of_log2;
}
printf("integral_part_of_log2 == %d\n", integral_part_of_log2);
// Calculate the denominator of -log(x/y).
long long yy = 1;
for (size_t j = N; j; --j) yy *= j*y;
// Calculate the numerator of -log(x/y).
long long xx = 0;
{
const long long y_minus_x = y - x;
for (size_t i = N; i; --i) {
long long term = 1;
size_t j = N;
for (; j > i; --j) {
term *= j*y;
}
term *= y_minus_x;
--j;
for (; j; --j) {
term *= j*y_minus_x;
}
xx += term;
}
}
// Convert log to log2.
xx *= Kx;
yy *= Ky;
// Restore the aforementioned offset.
for (; integral_part_of_log2; ++integral_part_of_log2) xx -= yy;
printf("log2(%lld/%lld) == %lld/%lld\n", x0, y, xx, yy);
printf("in floating point, this ratio of integers works out to %g\n",
(1.0*xx)/(1.0*yy));
printf("the CPU's floating-point unit computes the log2 to be %g\n",
log2((1.0*x0)/(1.0*y)));
return 0;
}
Running this on my machine with command-line arguments of 5 7, it outputs:
K == -1477/1024
x/y == 5/7
integral_part_of_log2 == 0
log2(5/7) == -42093223872/86740254720
in floating point, this ratio of integers works out to -0.485279
the CPU's floating-point unit computes the log2 to be -0.485427
Accuracy would be substantially improved by N = 12 and Ky = 1 << 20, but for that you need either thriftier code or more than 64 bits.
THRIFTIER CODE
Thriftier code, wanting more effort to write, might represent numerator and denominator in prime factors. For example, it might represent 500 as [2 0 3], meaning (22)(30)(53).
Yet further improvements might occur to your imagination.
AN ALTERNATE APPROACH
For an alternate approach, though it might not meet your requirements precisely as you have stated them, @phuclv has given the suggestion I would be inclined to follow if your program were mine: work the problem in reverse, guessing a value c/d for the logarithm and then computing 2^(c/d), presumably via a Newton-Raphson iteration. Personally, I like the Newton-Raphson approach better. See sect. 4.8 here (my original).
MATHEMATICAL BACKGROUND
Several sources including mine already linked explain the Taylor series underlying the first approach and the Newton-Raphson iteration of the second approach. The mathematics unfortunately is nontrivial, but there you have it. Good luck.
Related Topics
Using Scanf() in C++ Programs Is Faster Than Using Cin
How to Get the Ip Address of a Local Computer
Nice Way to Append a Vector to Itself
Sfinae to Check For Inherited Member Functions
Template Specialization of Particular Members
Behavior of Post Increment in Cout
Why Doesn't C++ Use Std::Nested_Exception to Allow Throwing from Destructor
In C/C++ What's the Simplest Way to Reverse the Order of Bits in a Byte
Create Wcf Service For Unmanaged C++ Clients
Smart Pointers: Who Owns the Object
Is the Size of Std::Array Defined by Standard