bit_manipulation Namespace Reference

for IO operations More...

Functions
uint64_t	next_higher_number (uint64_t x)
	The main function implements checking the next number.
bool	isPowerOfTwo (std ::int64_t n)
	The main function implements check for power of 2.

Detailed Description

for IO operations

Bit manipulation algorithms.

for io operations

storing the numbers

for assert

Bit manipulation algorithms

for assert for IO operations

Bit manipulation algorithms

for assert

Bit Manipulation algorithms

for std::min for assert for IO operations for limits of integral types for std::vector

Function Documentation

isPowerOfTwo()

bool bit_manipulation::isPowerOfTwo

(

std ::int64_t

n

)

The main function implements check for power of 2.

Parameters

n	is the number who will be checked

Returns

either true or false

                                 {  // int64_t is preferred over int so that
                                      // no Overflow can be there.
 
    return n > 0 && !(n & n - 1);  // If we subtract a power of 2 numbers by 1
    // then all unset bits after the only set bit become set; and the set bit
    // becomes unset.
 
    // If a number n is a power of 2 then bitwise and of n-1 and n will be zero.
    // The expression n&(n-1) will not work when n is 0.
    // To handle this case also, our expression will become n& (!n&(n-1))
}

next_higher_number()

uint64_t bit_manipulation::next_higher_number

(

uint64_t

x

)

The main function implements checking the next number.

Parameters

x	the number that will be calculated

Returns

a number

                                        {
    uint64_t rightOne = 0;
    uint64_t nextHigherOneBit = 0;
    uint64_t rightOnesPattern = 0;
 
    uint64_t next = 0;
 
    if (x) {
        // right most set bit
        rightOne = x & -static_cast<signed>(x);
 
        // reset the pattern and set next higher bit
        // left part of x will be here
        nextHigherOneBit = x + rightOne;
 
        // nextHigherOneBit is now part [D] of the above explanation.
 
        // isolate the pattern
        rightOnesPattern = x ^ nextHigherOneBit;
 
        // right adjust pattern
        rightOnesPattern = (rightOnesPattern) / rightOne;
 
        // correction factor
        rightOnesPattern >>= 2;
 
        // rightOnesPattern is now part [A] of the above explanation.
 
        // integrate new pattern (Add [D] and [A])
        next = nextHigherOneBit | rightOnesPattern;
    }
 
    return next;
}