-1

Consider the following code:

#include <string>
#include <iostream>

std::size_t preceding_pow2(std::size_t n)
{
    std::size_t k = 1;
    while (k > 0 && k < n) {
        k <<= 1;
    }
    return k >> 1;
}

int main(int argc, char* argv[])
{
    std::size_t n = argc > 1 ? std::stoull(argv[1]) : 1ULL << 6;
    for (std::size_t i = 0; i < n; ++i) {
        std::cout << i << " " << preceding_pow2(i) << std::endl;
    }
    return 0;
}

It produces the following result:

0 0
1 0
2 1
3 2
4 2
5 4
6 4
7 4
8 4
9 8
10 8
11 8
12 8
13 8
14 8
15 8
16 8
17 16
18 16
19 16
20 16
21 16
22 16
23 16
24 16
25 16
26 16
27 16
28 16
29 16
30 16
31 16
32 16
33 32
34 32
35 32
36 32
37 32
38 32
39 32
40 32
41 32
42 32
43 32
44 32
45 32
46 32
47 32
48 32
49 32
50 32
51 32
52 32
53 32
54 32
55 32
56 32
57 32
58 32
59 32
60 32
61 32
62 32
63 32

Which is:

  • For 0 as input, the output is 0
  • For 1 as input, the output is 0
  • If the input is a power of 2, it returns the preceding power of 2
  • If the input is not a power of 2, it returns the power of 2 that is less than this number

Would there be any faster way to implement that function for high performance code?

Vincent
  • 57,703
  • 61
  • 205
  • 388
  • 2
    Consider that you haven't asked a question... I'd be looking at a math answer rather than a loop / counting answer. Maybe `2 ^ floor(log2(n))` , however that translates to C++... but probably there's a bit-twiddling approach to take the highest set bit – TessellatingHeckler May 27 '17 at 01:09
  • 1
    Which is really odd for someone with that much reputation – 8bitwide May 27 '17 at 01:13
  • 1
    This looks to be a better fit for codereview. Might be some benefit to a look-up table rather than loop and shift – user4581301 May 27 '17 at 01:13
  • 1
    I'm voting to close this question as off-topic because it belongs on another stack exchange site not listed. – STLDev May 27 '17 at 01:16
  • Sorry, did not even notice that I didn't write the question... – Vincent May 27 '17 at 01:22
  • [Rounding up to next power of 2](https://stackoverflow.com/q/466204/995714) – phuclv May 27 '17 at 01:33

1 Answers1

1

You can rewrite your function with a bit twiddling hack:

std::size_t preceding_pow2(std::size_t v) {
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    return (++v) >> 1;
}

Demo.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523