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.
Logarithm base 2 in C language
You can also create a helper function which converts to any log base you wish:
Something like this:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
double
my_log(double x, int base) {
return log(x) / log(base);
}
int
main(void) {
double x = 42.0;
printf("log(%f) = %f\n", x, my_log(x, 2));
return 0;
}
Compiled with:
gcc -Wall -o logprog logprog.c -lm
Output:
log(42.000000) = 5.392317
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 can I calculate log base 2 in c++?
for example for log 3 in base 2
log (3) / log(2)
will do it.
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
cout << log(3.0) / log(2.0) << endl;
}
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.
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;
}
How to compute log base 2 using bitwise operators?
If you count shifting as a bitwise operator, this is easy.
You already know how to do it by successive division by 2.
x >> 1 is the same as x / 2 for any unsigned integer in C.
If you need to make this faster, you can do a "divide and conquer"—shift, say, 4 bits at a time until you reach 0, then go back and look at the last 4 bits. That means at most 16 shifts and 19 compares instead of 63 of each. Whether it's actually faster on a modern CPU, I couldn't say without testing. And you can take this a step farther, to first do groups of 16, then 4, then 1. Probably not useful here, but if you had some 1024-bit integers, it might be worth considering.
Calculating Log base 2
Math.Log(num) returns the log of base e
Math.Log(num, base) is probably what you are looking for.
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.
Related Topics
Opencv Videocapture Lag Due to the Capture Buffer
Is C/C++ Bool Type Always Guaranteed to Be 0 or 1 When Typecast'Ed to Int
Error: Jump to Case Label in Switch Statement
How Do Sizeof(Arr)/Sizeof(Arr[0]) Work
Sequence Points and Partial Order
What Are the Rules for the "..." Token in the Context of Variadic Templates
Class Template with Template Class Friend, What's Really Going on Here
Borderless Window Using Areo Snap, Shadow, Minimize Animation, and Shake
Lightweight Memory Leak Debugging on Linux
Iterate Through Struct and Class Members
What Does Template <Unsigned Int N> Mean
Is the Order of Iterating Through Std::Map Known (And Guaranteed by the Standard)
How to Statically Link Standard Library to My C++ Program