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