Line data Source code
1 : // Copyright (c) 2019-2021 Made to Order Software Corp. All Rights Reserved
2 : //
3 : // https://snapwebsites.org/project/snapdev
4 : // contact@m2osw.com
5 : //
6 : // This program is free software; you can redistribute it and/or modify
7 : // it under the terms of the GNU General Public License as published by
8 : // the Free Software Foundation; either version 2 of the License, or
9 : // (at your option) any later version.
10 : //
11 : // This program is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 : //
16 : // You should have received a copy of the GNU General Public License along
17 : // with this program; if not, write to the Free Software Foundation, Inc.,
18 : // 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 : #pragma once
20 :
21 : /** \file
22 : * \brief Calculate the log2() of an integer.
23 : *
24 : * This function calculates the number of zero bits before the first bit set
25 : * to 1. This is the floor of the log of a number in base 2 or:
26 : *
27 : * floor(log(n) / log(2))
28 : *
29 : * The function makes use of an intrinsic so that way it goes as fast as
30 : * possible which should be one CPU cycle to find the bit and another couple
31 : * of cycles to transform the number in the correct `log2()` value.
32 : *
33 : * The result could be used to do:
34 : *
35 : * 1 << log2(v)
36 : *
37 : * to find v against assuming v was an exact power of 2 to start with.
38 : */
39 :
40 : // C lib
41 : //
42 : #include <stdio.h>
43 :
44 :
45 : namespace snap
46 : {
47 :
48 :
49 : /** \brief Calculate the log2() of an integer.
50 : *
51 : * This function uses an intrinsic instruction to calculate the log2()
52 : * of a 64 bit integer. The lower bits are ignored.
53 : *
54 : * This is equivalent to finding the position of the first bit set starting
55 : * at bit 63 and going down to bit 0.
56 : *
57 : * Note that `log2(0)` is undefined. The function returns -1 in that case.
58 : *
59 : * If your number is signed, make sure to pass the absolute value:
60 : * `log2(llabs(v))`.
61 : *
62 : * Source:
63 : * https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers
64 : *
65 : * \param[in] v The integer to calculate the log2() from.
66 : *
67 : * \return `floor(log(v) / log(2))` or -1 when v == 0.
68 : */
69 129 : int log2(std::uint64_t v)
70 : {
71 129 : if(v == 0)
72 : {
73 1 : return -1;
74 : }
75 :
76 128 : return 63 - __builtin_clzll(v);
77 : }
78 :
79 :
80 :
81 : } // namespace snap
82 : // vim: ts=4 sw=4 et
|