powers of 2

[parzival69]

1)so we have the N amount of numbers for example : 3 then we have numbers 8 ,4 ,7 . And i want code which will be able to cout the amount of numbers which is the power of 2 from this list.

[parzival69]

P.S. Thanks in advance :)

[salem c]

Keep dividing by 2 until you get to 1.
If at any point, the number is odd, then it wasn't a power of 2.

[parzival69]

ty

[jonnin]

you can do it with a log base 2 if you want. (cmath log2() function, you don't even need the change of base stuff for the common logs (e, 2, and 10 for sure are supported, not sure what else).

all the powers of 2 are a single bit, right? 1 (2^0), 2 (10) 4 (100) 8 (1000) ... see any pattern you could exploit there? alternately you can use a lookup table (think <map>) -- there are only 64 values in a 64 bit number.

[lastchance]

#include <iostream>
using namespace std;

bool isPowerOfp( unsigned n, int p )
{
   return n == 1 || ( n > 1 && !( n % p ) && isPowerOfp( n / p, p ) );
}

int main()
{
   for ( int i = 0; i <= 32; i++ ) cout << i << ": " << boolalpha << isPowerOfp( i, 2 ) << '\n';
}

[Peter87]

In C++20 you will be able to use std::ispow2 to check if an integer is a power of two.

https://en.cppreference.com/w/cpp/numeric/ispow2

[Browni3141]

gcc has a function __builtin_popcount, which returns the number of bits set in a number. A positive power of two will have exactly one bit set when represented as ant integer.

if (__builtin_popcount(number) == 1)
    //number is a power of two. 

Something like this should work with any compiler and be very fast:

if ((number-1)&number == 0)
    //number is a power of two. 

It works because (number-1) toggles the leftmost bit only if number is a power of two.

#include <iostream>

int main()
{
    int n;
    while (std::cin >> n)
    {
        std::cout << n << " is " << ((n-1)&n ? " not " : "") << "a power of two.\n";
    }
    return 0;
}

Edit: this doesn't work on zero. You could fix this by checking if the number is zero.

[jonnin]

edit: I see it gives true for zero.
you can roll that into the existing condition, it does not have to be outside the existing code.

[mzimmers]

If I understand your problem, you want to determine whether a given value is a binomial coefficient? If this is correct:

while (bit 0 is 0)
{
shift one bit right;
}

shift one bit right; // get rid of the first "1"

if (value is 0)
{
number is a binomial coefficient
}
else
{
number is not a binomial coefficient
}

I'm also assuming your instructor wants you to do the work, rather than rely on a library call.

[tpb]

mzimmers wrote:

you want to determine whether a given value is a binomial coefficient?

"powers of 2" and "binomial coefficients" are two very different things.

Your answer will go into an inifinte loop if the input is 0. Even if it didn't, the final shift after the loop will cause it to consider 0 to be a power of 2. So maybe something like this:

bool is_pow2(unsigned long n) {
    while (n > 1 && n & 1 == 0)
        n >>= 1;
    return n == 1;
}

It's really just salem.c's idea translated from arithmetic to bitshifting operations.

[JLBorges]

I'm getting interesting performance results for these four methods.

#include <iostream>
#include <ctime>
#include <typeinfo>

#ifdef _MSC_VER

    #include <intrin.h>
    struct is_pow2_popcount {
        bool operator()( unsigned int n ) const { return __popcnt(n) == 1 ; }
    };

#else

    struct is_pow2_popcount {
        bool operator()( unsigned int n ) const { return __builtin_popcount(n) == 1 ; }
};

#endif // _MSC_VER

struct is_pow2_dec_and_cmp {
    bool operator() ( unsigned int n ) const { return n && ( (n-1)&n ) == 0 ; }
};

struct is_pow2_div_by_2 {

    bool operator() ( unsigned int n ) const {

        while( ( n%2 == 0 ) && ( n > 1U ) ) n /= 2U ;

        return n == 1U ;
    }
};

struct is_pow2_shift_right {

    bool operator() ( unsigned int n ) const {

        while( (n&1U) == 0  && n > 1U ) n >>= 1U ;

        return n == 1U ;
    }
};

template < typename FN > void time_it( FN is_pow2 ) {

    constexpr unsigned int NBITS = 28 ;
    constexpr unsigned int UBOUND = 1U << NBITS ;

    unsigned int cnt = 0 ;

    const auto start = std::clock() ;
    for( unsigned int i = 0 ; i < UBOUND ; ++i ) cnt += is_pow2(i) ;
    const auto end = std::clock() ;

    std::cout << cnt << " bits " << (end-start)*1000.0/CLOCKS_PER_SEC << " millisecs ("
              << typeid(is_pow2).name() << ")\n" ;
}

int main() {

    time_it( is_pow2_popcount{} ) ;
    time_it( is_pow2_dec_and_cmp{} ) ;
    time_it( is_pow2_div_by_2{} ) ;
    time_it( is_pow2_shift_right{} ) ;
}

g++ -O3 -march=native

28 bits 308.596 millisecs (16is_pow2_popcount)
28 bits 299.757 millisecs (19is_pow2_dec_and_cmp)
28 bits 1029.03 millisecs (16is_pow2_div_by_2)
28 bits 926.52 millisecs (19is_pow2_shift_right)

clang++ -O3 -march=native

28 bits 131.816 millisecs (16is_pow2_popcount)
28 bits 351.985 millisecs (19is_pow2_dec_and_cmp)
28 bits 2938.43 millisecs (16is_pow2_div_by_2)
28 bits 2926.64 millisecs (19is_pow2_shift_right)

Microsoft -Oi -Ox -arch

28 bits 389 millisecs (struct is_pow2_popcount)
28 bits 347 millisecs (struct is_pow2_dec_and_cmp)
28 bits 595 millisecs (struct is_pow2_div_by_2)
28 bits 600 millisecs (struct is_pow2_shift_right)

More Info
g++ and clang++: https://gcc.godbolt.org/z/vj4IvW
Microsoft: https://gcc.godbolt.org/z/ZlcXtf

[tpb]

That's interesting. So div_by_2 and shift_right are about the same, as we might suspect on a modern machine. But it's ridiculous that dec_and_cmp (a neat little trick) beats the intrinsic, which, if it can't use an appropriate CPU instruction should at least be able to use the dec_and_cmp trick itself (or is there a potential pitfall in that trick?). And clang++ seems to know something the others don't!

[Peter87]

But it's ridiculous that dec_and_cmp (a neat little trick) beats the intrinsic, which, if it can't use an appropriate CPU instruction should at least be able to use the dec_and_cmp trick itself (or is there a potential pitfall in that trick?).

The figures that JLBorges posted shows that popcount and dec_and_cmp are about the same with GCC. Have you done your own testing and found that this is not the case?

And clang++ seems to know something the others don't!

The Compiler Explorer link shows that both Clang and GCC generates the same code for is_pow2_popcount and is_pow2_dec_and_cmp, at least for that specific hardware. The difference seem to be that when the function is called inside a loop Clang decides to generate vector instructions (simd) while GCC doesn't. https://gcc.godbolt.org/z/P8x4SR

This sort of optimization will not be possible in all real-world use cases.

[tpb]

@Peter87,

I was just going by his results. You're right that for both GCC and MS they are very close, but I would've expected popcount to be faster as I was assuming there would be a CPU instruction for it. But I guess there isn't (at least on that machine).

That's interesting about clang and the vector instructions. Thanks for pointing that out. I guess I should've followed the links.

[JLBorges]

> when the function is called inside a loop Clang decides to generate vector instructions (simd)

Yes. Thanks, Peter87!

Haven't looked at the assembly; but from the numbers, it would appear that
MSVC has vectorised calls to is_pow2_div_by_2 and is_pow2_shift_right.

[JLBorges]

With shuffled data (when vectorisation is more expensive), builtin popcount appears to be even less attractive:

#include <iostream>
#include <ctime>
#include <typeinfo>
#include <numeric>
#include <algorithm>
#include <random>
#include <iterator>

#ifdef _MSC_VER

    #include <intrin.h>
    struct is_pow2_popcount {
        bool operator()( unsigned int n ) const { return __popcnt(n) == 1 ; }
    };

#else

    struct is_pow2_popcount {
        bool operator()( unsigned int n ) const { return __builtin_popcount(n) == 1 ; }
};

#endif // _MSC_VER

struct is_pow2_dec_and_cmp {
    bool operator() ( unsigned int n ) const { return n && ( (n-1)&n ) == 0 ; }
};

struct is_pow2_div_by_2 {

    bool operator() ( unsigned int n ) const {

        while( ( n%2 == 0 ) && ( n > 1U ) ) n /= 2U ;

        return n == 1U ;
    }
};

struct is_pow2_shift_right {

    bool operator() ( unsigned int n ) const {

        while( (n&1U) == 0  && n > 1U ) n >>= 1U ;

        return n == 1U ;
    }
};

constexpr std::size_t N = 1U << 24U ;
using data_set = unsigned int[N] ;

const data_set& numbers()
{
    static data_set a ;
    [[maybe_unused]] static const bool init = ( void( std::iota( std::begin(a), std::end(a), 0U ) ), true ) ;
    static std::mt19937 rng ; // not seeded
    [[maybe_unused]] static const bool init2 = ( void( std::shuffle( std::begin(a), std::end(a), rng ) ), true ) ;

    return a ;
}

template < typename FN > void time_it( FN is_pow2 ) {

    unsigned int cnt = 0 ;
    const auto& seq = numbers() ;

    const auto start = std::clock() ;
    for( unsigned int i : seq ) cnt += is_pow2(i) ;
    const auto end = std::clock() ;

    std::cout << cnt << " bits " << (end-start)*1000.0/CLOCKS_PER_SEC << " millisecs ("
              << typeid(is_pow2).name() << ")\n" ;
}

int main() {

    time_it( is_pow2_popcount{} ) ;
    time_it( is_pow2_dec_and_cmp{} ) ;
    time_it( is_pow2_div_by_2{} ) ;
    time_it( is_pow2_shift_right{} ) ;
}

g++ -O3 -march=native

24 bits 43.578 millisecs (16is_pow2_popcount)
24 bits 15.475 millisecs (19is_pow2_dec_and_cmp)
24 bits 144.636 millisecs (16is_pow2_div_by_2)
24 bits 159.008 millisecs (19is_pow2_shift_right)

clang++ -O3 -march=native

24 bits 22.635 millisecs (16is_pow2_popcount)
24 bits 14.203 millisecs (19is_pow2_dec_and_cmp)
24 bits 252.364 millisecs (16is_pow2_div_by_2)
24 bits 284.774 millisecs (19is_pow2_shift_right)

http://coliru.stacked-crooked.com/a/c358b6ff7d06c0ea

Microsoft -Oi -Ox -arch

24 bits 29 millisecs (struct is_pow2_popcount)
24 bits 33 millisecs (struct is_pow2_dec_and_cmp)
24 bits 171 millisecs (struct is_pow2_div_by_2)
24 bits 179 millisecs (struct is_pow2_shift_right)

https://rextester.com/XTEA68949

Assembly:
https://gcc.godbolt.org/z/P0m62x
https://gcc.godbolt.org/z/YQmPQW
https://gcc.godbolt.org/z/aG7d9b

[jonnin]

you guys have me beat so far. This is really cool. log and map both slower. I expected that for the map, but I thought log would actually be a contender.

I have a hackish contender :( its slower and uglier, but not that much slower.
and I just realized it isnt right either. Same bit set in 2 bytes and it will give the wrong answer. Back to the drawing board it is. Not going to beat a cpu instruction, regardless.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

union u { unsigned char c[8]; unsigned long long i; }; struct mapit{ static char tbl[256]; bool operator()( uint64_t in) { static u imau; imau.i = in; return tbl[(imau.c[0]|imau.c[1]|imau.c[2]|imau.c[3]|imau.c[4]|imau.c[5]|imau.c[6]|imau.c[7])]; } }; char mapit:: tbl[256] = {0};

main mapit::tbl[0] = 1; mapit::tbl[2] = 1; mapit::tbl[4] = 1; mapit::tbl[8] = 1; mapit::tbl[16] = 1; mapit::tbl[32] = 1; mapit::tbl[64] = 1; mapit::tbl[128] = 1; time_it( is_pow2_popcount{} ) ; time_it( is_pow2_dec_and_cmp{} ) ; time_it( is_pow2_div_by_2{} ) ; time_it( is_pow2_shift_right{} ) ; time_it(mapit{});

24 bits 31 millisecs (16is_pow2_
24 bits 16 millisecs (19is_pow2_
24 bits 140 millisecs (16is_pow2
24 bits 141 millisecs (19is_pow2
50 bits 47 millisecs (5mapit)


I think I am going to surrender this one. I was thinking there would be a way to do it in less N operations (adding up the bits, eg the shifting answer) without using the cpu instruction using logic but I can't find it. I was able to get it with a bit more work but it was a lot more than 8 operations (per byte) and a lot more expensive than the shifts which are so cheap.