Problem - 1: Compute the sign of an integer
sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then -1, else +1
Problem - 2: Compute the integer absolute value (abs) without branching
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v ^ mask) - mask; //r = (v < 0) ? -v : v,
Problem - 3: Compute the minimum (min) or maximum (max) of two integers without branching
r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)
r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)
Problem - 4: Determining if an integer is a power of 2
f = !(v & (v - 1)) && v;
Problem - 5: Conditionally set or clear bits without branching
bool f; // conditional flag
unsigned int m; // the bit mask
unsigned int w; // the word to modify: if (f) w |= m; else w &= ~m;
w ^= (-f ^ w) & m;
Problem - 6: Count number of bits set in an Intger
Approach -1 Brian Kernighan's way
for (c = 0; v; v >>= 1)
{
c += v & 1;
}
Approach -2static inline ulong bit_count(ulong x)
// Return number of bits set
{
x = (0x55555555UL & x) + (0x55555555UL & (x>> 1)); // 0-2 in 2 bits
x = (0x33333333UL & x) + (0x33333333UL & (x>> 2)); // 0-4 in 4 bits
x = (0x0f0f0f0fUL & x) + (0x0f0f0f0fUL & (x>> 4)); // 0-8 in 8 bits
x = (0x00ff00ffUL & x) + (0x00ff00ffUL & (x>> 8)); // 0-16 in 16 bits
x = (0x0000ffffUL & x) + (0x0000ffffUL & (x>>16)); // 0-31 in 32 bits
return x;
}
Approach -3
static inline ulong bit_count(ulong x)
{// Return number of bits set
x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
x += x >> 8; // 0-16 in 8 bits
x += x >> 16; // 0-32 in 8 bits
return x & 0xff;
}
Approach - 4
static inline ulong bit_count(ulong x)
{ // Return number of bits set
x -= (x>>1) & 0x55555555UL; // 0-2 in 2 bits
x = ((x>>2) & 0x33333333UL) + (x & 0x33333333UL); // 0-4 in 4 bits
x = ((x>>4) + x) & 0x0f0f0f0fUL; // 0-8 in 8 bits
x *= 0x01010101UL;
return x>>24;
}Problem - 7: Computing parity the naive way
unsigned int v; // word value to compute the parity of
bool parity = false; // parity will be the parity of b
while (v)
{
parity = !parity;
v = v & (v - 1);
}
Problem - 8: Swapping values with XOR
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
Problem - 9: Swapping individual bits with XOR
unsigned int i, j; // positions of bit sequences to swap
unsigned int n; // number of consecutive bits in each sequence
unsigned int b; // bits to swap reside in b
unsigned int r; // bit-swapped result goes here
int x = ((b >> i) ^ (b >> j)) & ((1 << n) - 1); // XOR temporary
r = b ^ ((x << i) | (x << j));
As an example of swapping ranges of bits suppose we have have
b = 00101111 (expressed in binary) and we want to swap the n = 3
consecutive bits starting at i = 1 (the second bit from the right)
with the 3 consecutive bits starting at j = 5; the result would b
e r = 11100011 (binary).
Problem - 10: Compute modulus division by 1 << s without a division operator
const unsigned int n; // numerator
const unsigned int s;
const unsigned int d = 1 << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ...
unsigned int m; // m will be n % d
m = n & (d - 1);
Problem - 11: Compute modulus division by (1 << s) - 1 without a division operator
unsigned int n; // numerator
const unsigned int s; // s > 0
const unsigned int d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
unsigned int m; // n % d goes here.
for (m = n; n > d; n = m)
{
for (m = 0; n; n >>= s)
{
m += n & d;
}
}
// Now m is s >>= 1) // unroll for more speed...
{
r++;
}
Problem - 12: int CheckSetBit(int num, int pos)
{
int x = 1;
x = ~(x<// creating mask in which only pos bit is unset
return ((num & x) == num); // checking whether number is same... if same then pos bit is set
}
Problem - 13: How to reverse the odd bits of an integer?
XOR each of its 4 hex parts with 0101.
inline ulong reverse_bit(ulong a, ulong i)
{
return (a ^ 0x55555555);
}Problem - 14: inline ulong change_bit(ulong a, ulong i)
// Return a with bit[i] changed.
{
return (a ^ (1UL << i));
}
Problem - 15: Swap k1 bits of integer a with its k2 bits
static inline ulong bit_swap(ulong a, ulong k1, ulong k2)
// Return a with bits at positions [k1] and [k2] swapped.
// k1==k2 is allowed (a is unchanged then)
{
ulong x = ((a>>k1) ^ (a>>k2)) & 1; // one if bits differ
a ^= (x<// change if bits differ
a ^= (x<// change if bits differ
return a;
}
Problem - 16: Return word where only the lowest set bit in x is set. Return 0 if no bit is set.
static inline ulong lowest_bit(ulong x)
{
return x & -x; // use: -x == ~x + 1
}
Problem - 17: Return word where only the lowest unset bit in x is set. Return 0 if all bits are set.
static inline ulong lowest_zero(ulong x)
{
x = ~x;
return x & -x;
}
Problem - 18: Return word were the lowest bit set in x is cleared. Return 0 for input == 0.
static inline ulong delete_lowest_bit(ulong x)
{
return x & (x-1);
}
Problem - 19: Return word were the lowest unset bit in x is set. Return ~0 for input == ~0.
static inline ulong set_lowest_zero(ulong x)
{
return x | (x+1);
}
Problem - 20: static inline ulong low_bits(ulong x)
// Return word where all the (low end) ones are set.
// Example: 01011011 --> 00000011
// Return 0 if lowest bit is zero:
// 10110110 --> 0
{
if ( ~0UL==x ) return ~0UL;
return (((x+1)^x) >> 1);
}
Problem - 21: Return word where all the (low end) zeros are set.
Example: 01011000 --> 00000111
Return 0 if all bits are set.
static inline ulong low_zeros(ulong x)
{
if ( 0==x ) return ~0UL;
return (((x-1)^x) >> 1);
}
Problem - 22: in order to determine whether x is a prime less than 32, one can use the function
ulong m = (1UL<<2) | (1UL<<3) | (1UL<<5) | ... | (1UL<<31); // precomputed
static inline ulong is_tiny_prime(ulong x)
{
return m & (1UL << x);
}
Problem - 23: Computation of the average (x + y)/2 of two arguments x and y. The function gives the correct value even if (x + y) does not fit into a machine word:
static inline ulong average(ulong x, ulong y)
// Return (x+y)/2
// Use the fact that x+y == ((x&y)<<1) + (x^y)
// that is: sum == carries + sum_without_carries
{
return (x & y) + ((x ^ y) >> 1);
}
Problem - 24: static inline ulong bit_rotate_left(ulong x, ulong r)
// Return word rotated r bits to the left
// (i.e. toward the most significant bit)
{
return (x<>(BITS_PER_LONG-r));
}
Problem - 25: When swapping half-words (here for 32-bit architectures)
static inline ulong bit_swap_16(ulong x)
// Return x with groups of 16 bits swapped.
{
ulong m = 0x0000ffffUL;
return ((x & m) << 16) | ((x & (m<<16)) >> 16);
}
Problem - 26: The 64-bit branch is omitted in the following examples. Adjacent groups of 2 bits are swapped bystatic inline ulong bit_swap_1(ulong x)
// Return x with groups of 2 bits swapped.
{
ulong m = 0x55555555UL;
return ((x & m) << 1) | ((x & (~m)) >> 1);
}
static inline ulong bit_swap_2(ulong x)
// Return x with groups of 2 bits swapped.
{
ulong m = 0x33333333UL;
return ((x & m) << 2) | ((x & (~m)) >> 2);
}
Equivalently,
static inline ulong bit_swap_4(ulong x)
// Return x with groups of 4 bits swapped.
{
ulong m = 0x0f0f0f0fUL;
return ((x & m) << 4) | ((x & (~m)) >> 4);
}
and
static inline ulong bit_swap_8(ulong x)
// Return x with groups of 8 bits swapped.
{
ulong m = 0x00ff00ffUL;
return ((x & m) << 8) | ((x & (~m)) >> 8);
}
Problem - 27: Reverse the bits of an integer
static inline ulong revbin(ulong x)
// Return x with bitsequence reversed
{
x = bit_swap_1(x);
x = bit_swap_2(x);
x = bit_swap_4(x);
x = bit_swap_8(x);
x = bit_swap_16(x);
//x = bit_swap_32(x); required only when m/c is 64 bit
return x;
}
Problem - 28: Reverse bits the obvious way
unsigned int v; // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end
for (v >>= 1; v; v >>= 1)
{
r <<= 1;
r |= v & 1;
s--;
}
r <<= s; // shift when v's highest bits are zeroProblem - 29: Add to numbers
sum = A ^ B
carry A&B
crud way a-(-B)
Problem - 30: Dump binary
void print(ulong v)
{
cout << "BIN:";
int s = 32;
while (s--)
{
cout <<((v & 0x80000000UL) >> 31);
v <<= 1;
}
cout << endl;
}
Problem - 32: How would you add/Subtract 1 to a number without using the arithmetic operators
int x=16;
int m=1;
while( !( x & m))
{
x=x^m;
m<<=1;
}
x=x^m;
Change the while condition to while( x & m ) to add one to a number
Problem - 33: Upper case to Lower case and vice-verse.
Below code will toggle the case -
void chage_case(string& str) {
string::const_iterator it = str.begin();
while (it != str.end()) {
// key here is XORing any character with 0x20 will change its case
*it = *it ^ 0x20;
}
}
sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then -1, else +1
Problem - 2: Compute the integer absolute value (abs) without branching
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v ^ mask) - mask; //r = (v < 0) ? -v : v,
Problem - 3: Compute the minimum (min) or maximum (max) of two integers without branching
r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)
r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)
Problem - 4: Determining if an integer is a power of 2
f = !(v & (v - 1)) && v;
Problem - 5: Conditionally set or clear bits without branching
bool f; // conditional flag
unsigned int m; // the bit mask
unsigned int w; // the word to modify: if (f) w |= m; else w &= ~m;
w ^= (-f ^ w) & m;
Problem - 6: Count number of bits set in an Intger
Approach -1 Brian Kernighan's way
for (c = 0; v; v >>= 1)
{
c += v & 1;
}
Approach -2static inline ulong bit_count(ulong x)
// Return number of bits set
{
x = (0x55555555UL & x) + (0x55555555UL & (x>> 1)); // 0-2 in 2 bits
x = (0x33333333UL & x) + (0x33333333UL & (x>> 2)); // 0-4 in 4 bits
x = (0x0f0f0f0fUL & x) + (0x0f0f0f0fUL & (x>> 4)); // 0-8 in 8 bits
x = (0x00ff00ffUL & x) + (0x00ff00ffUL & (x>> 8)); // 0-16 in 16 bits
x = (0x0000ffffUL & x) + (0x0000ffffUL & (x>>16)); // 0-31 in 32 bits
return x;
}
Approach -3
static inline ulong bit_count(ulong x)
{// Return number of bits set
x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
x += x >> 8; // 0-16 in 8 bits
x += x >> 16; // 0-32 in 8 bits
return x & 0xff;
}
Approach - 4
static inline ulong bit_count(ulong x)
{ // Return number of bits set
x -= (x>>1) & 0x55555555UL; // 0-2 in 2 bits
x = ((x>>2) & 0x33333333UL) + (x & 0x33333333UL); // 0-4 in 4 bits
x = ((x>>4) + x) & 0x0f0f0f0fUL; // 0-8 in 8 bits
x *= 0x01010101UL;
return x>>24;
}Problem - 7: Computing parity the naive way
unsigned int v; // word value to compute the parity of
bool parity = false; // parity will be the parity of b
while (v)
{
parity = !parity;
v = v & (v - 1);
}
Problem - 8: Swapping values with XOR
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
Problem - 9: Swapping individual bits with XOR
unsigned int i, j; // positions of bit sequences to swap
unsigned int n; // number of consecutive bits in each sequence
unsigned int b; // bits to swap reside in b
unsigned int r; // bit-swapped result goes here
int x = ((b >> i) ^ (b >> j)) & ((1 << n) - 1); // XOR temporary
r = b ^ ((x << i) | (x << j));
As an example of swapping ranges of bits suppose we have have
b = 00101111 (expressed in binary) and we want to swap the n = 3
consecutive bits starting at i = 1 (the second bit from the right)
with the 3 consecutive bits starting at j = 5; the result would b
e r = 11100011 (binary).
Problem - 10: Compute modulus division by 1 << s without a division operator
const unsigned int n; // numerator
const unsigned int s;
const unsigned int d = 1 << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ...
unsigned int m; // m will be n % d
m = n & (d - 1);
Problem - 11: Compute modulus division by (1 << s) - 1 without a division operator
unsigned int n; // numerator
const unsigned int s; // s > 0
const unsigned int d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
unsigned int m; // n % d goes here.
for (m = n; n > d; n = m)
{
for (m = 0; n; n >>= s)
{
m += n & d;
}
}
// Now m is s >>= 1) // unroll for more speed...
{
r++;
}
Problem - 12: int CheckSetBit(int num, int pos)
{
int x = 1;
x = ~(x<
return ((num & x) == num); // checking whether number is same... if same then pos bit is set
}
Problem - 13: How to reverse the odd bits of an integer?
XOR each of its 4 hex parts with 0101.
inline ulong reverse_bit(ulong a, ulong i)
{
return (a ^ 0x55555555);
}Problem - 14: inline ulong change_bit(ulong a, ulong i)
// Return a with bit[i] changed.
{
return (a ^ (1UL << i));
}
Problem - 15: Swap k1 bits of integer a with its k2 bits
static inline ulong bit_swap(ulong a, ulong k1, ulong k2)
// Return a with bits at positions [k1] and [k2] swapped.
// k1==k2 is allowed (a is unchanged then)
{
ulong x = ((a>>k1) ^ (a>>k2)) & 1; // one if bits differ
a ^= (x<
a ^= (x<
return a;
}
Problem - 16: Return word where only the lowest set bit in x is set. Return 0 if no bit is set.
static inline ulong lowest_bit(ulong x)
{
return x & -x; // use: -x == ~x + 1
}
Problem - 17: Return word where only the lowest unset bit in x is set. Return 0 if all bits are set.
static inline ulong lowest_zero(ulong x)
{
x = ~x;
return x & -x;
}
Problem - 18: Return word were the lowest bit set in x is cleared. Return 0 for input == 0.
static inline ulong delete_lowest_bit(ulong x)
{
return x & (x-1);
}
Problem - 19: Return word were the lowest unset bit in x is set. Return ~0 for input == ~0.
static inline ulong set_lowest_zero(ulong x)
{
return x | (x+1);
}
Problem - 20: static inline ulong low_bits(ulong x)
// Return word where all the (low end) ones are set.
// Example: 01011011 --> 00000011
// Return 0 if lowest bit is zero:
// 10110110 --> 0
{
if ( ~0UL==x ) return ~0UL;
return (((x+1)^x) >> 1);
}
Problem - 21: Return word where all the (low end) zeros are set.
Example: 01011000 --> 00000111
Return 0 if all bits are set.
static inline ulong low_zeros(ulong x)
{
if ( 0==x ) return ~0UL;
return (((x-1)^x) >> 1);
}
Problem - 22: in order to determine whether x is a prime less than 32, one can use the function
ulong m = (1UL<<2) | (1UL<<3) | (1UL<<5) | ... | (1UL<<31); // precomputed
static inline ulong is_tiny_prime(ulong x)
{
return m & (1UL << x);
}
Problem - 23: Computation of the average (x + y)/2 of two arguments x and y. The function gives the correct value even if (x + y) does not fit into a machine word:
static inline ulong average(ulong x, ulong y)
// Return (x+y)/2
// Use the fact that x+y == ((x&y)<<1) + (x^y)
// that is: sum == carries + sum_without_carries
{
return (x & y) + ((x ^ y) >> 1);
}
Problem - 24: static inline ulong bit_rotate_left(ulong x, ulong r)
// Return word rotated r bits to the left
// (i.e. toward the most significant bit)
{
return (x<
}
Problem - 25: When swapping half-words (here for 32-bit architectures)
static inline ulong bit_swap_16(ulong x)
// Return x with groups of 16 bits swapped.
{
ulong m = 0x0000ffffUL;
return ((x & m) << 16) | ((x & (m<<16)) >> 16);
}
Problem - 26: The 64-bit branch is omitted in the following examples. Adjacent groups of 2 bits are swapped bystatic inline ulong bit_swap_1(ulong x)
// Return x with groups of 2 bits swapped.
{
ulong m = 0x55555555UL;
return ((x & m) << 1) | ((x & (~m)) >> 1);
}
static inline ulong bit_swap_2(ulong x)
// Return x with groups of 2 bits swapped.
{
ulong m = 0x33333333UL;
return ((x & m) << 2) | ((x & (~m)) >> 2);
}
Equivalently,
static inline ulong bit_swap_4(ulong x)
// Return x with groups of 4 bits swapped.
{
ulong m = 0x0f0f0f0fUL;
return ((x & m) << 4) | ((x & (~m)) >> 4);
}
and
static inline ulong bit_swap_8(ulong x)
// Return x with groups of 8 bits swapped.
{
ulong m = 0x00ff00ffUL;
return ((x & m) << 8) | ((x & (~m)) >> 8);
}
Problem - 27: Reverse the bits of an integer
static inline ulong revbin(ulong x)
// Return x with bitsequence reversed
{
x = bit_swap_1(x);
x = bit_swap_2(x);
x = bit_swap_4(x);
x = bit_swap_8(x);
x = bit_swap_16(x);
//x = bit_swap_32(x); required only when m/c is 64 bit
return x;
}
Problem - 28: Reverse bits the obvious way
unsigned int v; // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end
for (v >>= 1; v; v >>= 1)
{
r <<= 1;
r |= v & 1;
s--;
}
r <<= s; // shift when v's highest bits are zeroProblem - 29: Add to numbers
sum = A ^ B
carry A&B
crud way a-(-B)
Problem - 30: Dump binary
void print(ulong v)
{
cout << "BIN:";
int s = 32;
while (s--)
{
cout <<((v & 0x80000000UL) >> 31);
v <<= 1;
}
cout << endl;
}
Problem - 31: Give me the best way to multiply an integer by 3.5.
There are many solutions to this but (x>>1)+x+(x<<1) is the best since it is least prone to overflowing.
(num<<3 - num)>>1
This is multiply the number by 7 and divide by 2 - > may cause overflow since there is right shifted 3 timesProblem - 32: How would you add/Subtract 1 to a number without using the arithmetic operators
int x=16;
int m=1;
while( !( x & m))
{
x=x^m;
m<<=1;
}
x=x^m;
Change the while condition to while( x & m ) to add one to a number
Problem - 33: Upper case to Lower case and vice-verse.
Below code will toggle the case -
void chage_case(string& str) {
string::const_iterator it = str.begin();
while (it != str.end()) {
// key here is XORing any character with 0x20 will change its case
*it = *it ^ 0x20;
}
}
No comments:
Post a Comment