Skip to content

Instantly share code, notes, and snippets.

@activedecay

activedecay/bithacks.c

Last active April 20, 2022 06:22
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save activedecay/f2e1d1f47cfbabf27b206515c623fbe9 to your computer and use it in GitHub Desktop.
Save activedecay/f2e1d1f47cfbabf27b206515c623fbe9 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
bithacks.c
/** By_Sean_Eron_Anderson seander@cs.stanford.edu */
#include <stdbool.h>
#include <stdint.h>
#include <endian.h>
#define CHAR_BIT 8
void Compute_the_sign_of_an_integer() {
/*Compute the sign of an integer*/
int v; // we want to find the sign of v
int sign; // the result goes here
//CHAR_BIT is the number of bits per byte (normally 8).
sign = -(v < 0); // if v < 0 then -1, else 0.
//or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int) ((unsigned int) ((int) v) >> (sizeof(int) * CHAR_BIT - 1));
//or, for one less instruction (but not portable):
sign = v >> (sizeof(int) * CHAR_BIT - 1);
/*Alternatively, if you prefer the result be either -1 or +1, then use:*/
sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then -1, else +1
/*On the other hand, if you prefer the result be either -1, 0, or +1, then use:*/
sign = (v != 0) | -(int) ((unsigned int) ((int) v) >> (sizeof(int) * CHAR_BIT - 1));
//Or, for more speed but less portability:
sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT - 1)); // -1, 0, or +1
//Or, for portability, brevity, and (perhaps) speed:
sign = (v > 0) - (v < 0); // -1, 0, or +1
/*
If instead you want to know if something is non-negative, resulting in +1 or
else 0, then use:
*/
sign = 1 ^ ((unsigned int) v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then 0, else 1
}
void Detect_if_two_integers_have_opposite_signs() {
/*Detect if two integers have opposite signs*/
int x, y; // input values to compare signs
bool f = ((x ^ y) < 0); // true iff x and y have opposite signs
}
void Compute_the_integer_absolute_value____abs____without_branching() {
/*Compute the integer absolute value (abs) without branching*/
int v; // we want to find the absolute value of v
unsigned int r; // the result goes here
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v + mask) ^ mask;
/*
Patented variation:
*/
r = (v ^ mask) - mask;
}
void Compute_the_minimum____min____or_maximum____max____of_two_integers_without_branching() {
/*Compute the minimum (min) or maximum (max) of two integers without branching*/
int x; // we want to find the minimum of x and y
int y;
int r; // the result goes here
r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
/*To find the maximum, use:*/
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
/*
If you know that INT_MIN <= x - y <= INT_MAX,
then you can use the following, which
are faster because (x - y) only needs to be evaluated once.
*/
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)
}
void Determining_if_an_integer_is_a_power_of_2() {
/*Determining if an integer is a power of 2*/
unsigned int v; // we want to see if v is a power of 2
bool f; // the result goes here
f = (v & (v - 1)) == 0;
/*
Note that 0 is incorrectly considered a power of 2 here. To remedy
this, use:
*/
f = v && !(v & (v - 1));
}
void Sign_extending_from_a_constant_bitwidth() {
/*
Sign extension is automatic for built-in types, such as chars and ints.
But suppose you have a signed two's complement number, x, that is stored
using only b bits. Moreover, suppose you want to convert x to an int,
which has more than b bits. A simple copy will work if x
is positive, but if negative, the sign must be extended. For example,
if we have only 4 bits to store a number, then -3 is represented as 1101
in binary. If we have 8 bits, then -3 is 11111101. The most-significant
bit of the 4-bit representation is replicated sinistrally to fill
in the destination when we convert to a representation with more bits;
this is sign extending.
In C, sign extension from a constant bit-width is trivial, since bit
fields may be specified in structs or unions.
For example, to convert from 5 bits to an full integer:
*/
int x; // convert this from using 5 bits to a full int
int r; // resulting sign extended number goes here
struct {
signed int x:5;
} s;
r = s.x = x;
/*
The following is a C++ template function that uses the same
language feature to convert from B bits in one operation (though
the compiler is generating more, of course).
*/
//C++ is garbage.
// template <typename T, unsigned B>
// inline T signextend(const T x)
// {
// struct {T x:B;} s;
// return s.x = x;
// }
// int r = signextend<signed int,5>(x); // sign extend 5 bit number x to r
}
void Sign_extending_from_a_variable_bitwidth() {
/*
Sometimes we need to extend the sign of a number but we don't know a priori
the number of bits, b, in which it is represented. (Or we could be
programming in a language like Java, which lacks bitfields.)
*/
unsigned b; // number of bits representing the number in x
int x; // sign extend this b-bit number to r
int r; // resulting sign-extended number
int const m = 1U << (b - 1); // mask can be pre-computed if b is fixed
x = x & ((1U << b) - 1); // (Skip this if bits in x above position b are already zero.)
r = (x ^ m) - m;
}
void Sign_extending_from_a_variable_bitwidth2() {
unsigned b; // number of bits representing the number in x
int x; // sign extend this b-bit number to r
int r; // resulting sign-extended number
/*A slightly faster but less portable method that doesn't depend on the bits in x above position b being zero is:*/
int const m = CHAR_BIT * sizeof(x) - b;
r = (x << m) >> m;
}
void Sign_extending_from_a_variable_bitwidth_in_3_operations() {
/*
The following may be slow on some machines, due to the effort required for
multiplication and division. This version is 4 operations. If you
know that your initial bit-width, b, is greater than 1, you might do this
type of sign extension in 3 operations by using
r = (x * multipliers[b]) / multipliers[b],
which requires only one array lookup.
*/
unsigned b; // number of bits representing the number in x
int x; // sign extend this b-bit number to r
int r; // resulting sign-extended number
#define M(B) (1U << ((sizeof(x) * CHAR_BIT) - B)) // CHAR_BIT=bits/byte
static int const multipliers[] =
{
0, M(1), M(2), M(3), M(4), M(5), M(6), M(7),
M(8), M(9), M(10), M(11), M(12), M(13), M(14), M(15),
M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
M(32)
}; // (add more if using more than 64 bits)
static int const divisors[] =
{
1, ~M(1), M(2), M(3), M(4), M(5), M(6), M(7),
M(8), M(9), M(10), M(11), M(12), M(13), M(14), M(15),
M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
M(32)
}; // (add more for 64 bits)
#undef M
r = (x * multipliers[b]) / divisors[b];
/*
The following variation is not portable,
but on architectures that employ an arithmetic right-shift,
maintaining the sign, it should be fast.
*/
const int s = -b; // OR: sizeof(x) * CHAR_BIT - b;
r = (x << s) >> s;
}
void Conditionally_set_or_clear_bits_without_branching() {
/*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;
//OR, for superscalar CPUs:
w = (w & ~m) | (-f & m);
}
void Conditionally_negate_a_value_without_branching() {
/*
If you need to negate only when a flag is false, then use the following
to avoid branching:
*/
bool fDontNegate; // Flag indicating we should not negate v.
int v; // Input value to negate if fDontNegate is false.
int r; // result = fDontNegate ? v : -v;
r = (fDontNegate ^ (fDontNegate - 1)) * v;
}
void Conditionally_negate_a_value_without_branching2() {
/*
If you need to negate only when a flag is true, then use this:
*/
bool fNegate; // Flag indicating if we should negate v.
int v; // Input value to negate if fNegate is true.
int r; // result = fNegate ? -v : v;
r = (v ^ -fNegate) + fNegate;
}
void Merge_bits_from_two_values_according_to_a_mask() {
/*Merge bits from two values according to a mask*/
unsigned int a; // value to merge in non-masked bits
unsigned int b; // value to merge in masked bits
unsigned int mask; // 1 where bits from b should be selected; 0 where from a.
unsigned int r; // result of (a & ~mask) | (b & mask) goes here
r = a ^ ((a ^ b) & mask);
}
void Counting_bits_set____naive_way___() {
/*Counting bits set (naive way)*/
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; v >>= 1) {
c += v & 1;
}
}
void Counting_bits_set_by_lookup_table() {
/*Counting bits set by lookup table*/
static const unsigned char BitsSetTable256[256] =
{
# define B2(n) n, n+1, n+1, n+2
# define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
# define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
B6(0), B6(1), B6(1), B6(2)
};
unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v
//Option 1:
c = BitsSetTable256[v & 0xff] +
BitsSetTable256[(v >> 8) & 0xff] +
BitsSetTable256[(v >> 16) & 0xff] +
BitsSetTable256[v >> 24];
//Option 2:
unsigned char *p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] +
BitsSetTable256[p[1]] +
BitsSetTable256[p[2]] +
BitsSetTable256[p[3]];
}
void Counting_bits_set_by_lookup_table2() {
static unsigned char BitsSetTable256[256] = {};
//To initially generate the table algorithmically:
// BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++) {
BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}
}
void Counting_bits_set_Brian_Kernighans_way() {
/*Counting bits set, Brian Kernighan's way*/
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++) {
v &= v - 1; // clear the least significant bit set
}
}
void Counting_bits_set_in_14_24_or_32bit_words_using_64bit_instructions() {
/*Counting bits set in 14, 24, or 32-bit words using 64-bit instructions*/
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
//option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
//option 2, for at most 24-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)
% 0x1f;
//option 3, for at most 32-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %
0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
}
void Counting_bits_set_in_parallel() {
/*Counting bits set, in parallel*/
unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
static int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
c = v - ((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];
/*
The B array, expressed as binary, is:
*/
B[0] = 0x55555555; /* = 01010101 01010101 01010101 01010101*/
B[1] = 0x33333333; /* = 00110011 00110011 00110011 00110011*/
B[2] = 0x0F0F0F0F; /* = 00001111 00001111 00001111 00001111*/
B[3] = 0x00FF00FF; /* = 00000000 11111111 00000000 11111111*/
B[4] = 0x0000FFFF; /* = 00000000 00000000 11111111 11111111*/
/*The best method for counting bits in a 32-bit integer v is the following:*/
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
///*A generalization of the best bit counting method to integers of bit-widths upto 128 (parameterized by type T) is this:*/
// v = v - ((v >> 1) & (T)~(T)0/3); // temp
// v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); // temp
// v = (v + (v >> 4)) & (T)~(T)0/255*15; // temp
// c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count
}
void Count_bits_set____rank____from_the_mostsignificant_bit_upto_a_given_position() {
/*
The following finds the the rank of a bit, meaning it returns the sum of
bits that are set to 1 from the most-signficant bit downto the bit at
the given position.
*/
uint64_t v; // Compute the rank (bits set) in v from the MSB to pos.
unsigned int pos; // Bit position to count bits upto.
uint64_t r; // Resulting rank of bit at pos goes here.
// Shift out bits after given position.
r = v >> (sizeof(v) * CHAR_BIT - pos);
// Count set bits in parallel.
// r = (r & 0x5555...) + ((r >> 1) & 0x5555...);
r = r - ((r >> 1) & ~0UL / 3);
// r = (r & 0x3333...) + ((r >> 2) & 0x3333...);
r = (r & ~0UL / 5) + ((r >> 2) & ~0UL / 5);
// r = (r & 0x0f0f...) + ((r >> 4) & 0x0f0f...);
r = (r + (r >> 4)) & ~0UL / 17;
// r = r % 255;
r = (r * (~0UL / 255)) >> ((sizeof(v) - 1) * CHAR_BIT);
}
void Select_the_bit_position____from_the_mostsignificant_bit____with_the_given_count____rank___() {
/* 1 bit
when counting from the left. In other words if we start
at the most significant bit and proceed to the right,
counting the number of bits set to 1 until we reach the desired rank, r,
then the position where we stop is returned. If the rank requested exceeds
the count of bits set, then 64 is returned.
The code may be modified for 32-bit or counting from the right.
*/
uint64_t v; // Input value to find position with rank r.
unsigned int r; // Input: bit's desired rank [1-64].
unsigned int s; // Output: Resulting position of bit with rank r [1-64]
uint64_t a, b, c, d; // Intermediate temporaries for bit count.
unsigned int t; // Bit count temporary.
// Do a normal parallel bit count for a 64-bit integer,
// but store all intermediate steps.
// a = (v & 0x5555...) + ((v >> 1) & 0x5555...);
a = v - ((v >> 1) & ~0UL / 3);
// b = (a & 0x3333...) + ((a >> 2) & 0x3333...);
b = (a & ~0UL / 5) + ((a >> 2) & ~0UL / 5);
// c = (b & 0x0f0f...) + ((b >> 4) & 0x0f0f...);
c = (b + (b >> 4)) & ~0UL / 0x11;
// d = (c & 0x00ff...) + ((c >> 8) & 0x00ff...);
d = (c + (c >> 8)) & ~0UL / 0x101;
t = (d >> 32) + (d >> 48);
// Now do branchless select!
s = 64;
// if (r > t) {s -= 32; r -= t;}
s -= ((t - r) & 256) >> 3;
r -= (t & ((t - r) >> 8));
t = (d >> (s - 16)) & 0xff;
// if (r > t) {s -= 16; r -= t;}
s -= ((t - r) & 256) >> 4;
r -= (t & ((t - r) >> 8));
t = (c >> (s - 8)) & 0xf;
// if (r > t) {s -= 8; r -= t;}
s -= ((t - r) & 256) >> 5;
r -= (t & ((t - r) >> 8));
t = (b >> (s - 4)) & 0x7;
// if (r > t) {s -= 4; r -= t;}
s -= ((t - r) & 256) >> 6;
r -= (t & ((t - r) >> 8));
t = (a >> (s - 2)) & 0x3;
// if (r > t) {s -= 2; r -= t;}
s -= ((t - r) & 256) >> 7;
r -= (t & ((t - r) >> 8));
t = (v >> (s - 1)) & 0x1;
// if (r > t) s--;
s -= ((t - r) & 256) >> 8;
s = 65 - s;
}
void Computing_parity_the_naive_way() {
/*Computing parity the naive way*/
unsigned int v; // word value to compute the parity of
bool parity = false; // parity will be the parity of v
while (v) {
parity = !parity;
v = v & (v - 1);
}
}
/*Compute parity by lookup table*/
static const bool ParityTable256[256] =
{
# define P2(n) n, n^1, n^1, n
# define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
# define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
P6(0), P6(1), P6(1), P6(0)
};
void Compute_parity_by_lookup_table() {
unsigned char b; // byte value to compute the parity of
bool parity = ParityTable256[b];
}
void Compute_parity_by_lookup_table2() {
//OR, for 32-bit words:
unsigned int v;
v ^= v >> 16;
v ^= v >> 8;
bool parity = ParityTable256[v & 0xff];
//Variation:
unsigned char *p = (unsigned char *) &v;
parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]];
}
void Compute_parity_of_a_byte_using_64bit_multiply_and_modulus_division() {
/*Compute parity of a byte using 64-bit multiply and modulus division*/
unsigned char b; // byte value to compute the parity of
bool parity =
(((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;
}
unsigned int Compute_parity_of_word_with_a_multiply() {
/*
The following method computes the parity of the 32-bit value in only 8
operations using a multiply.
*/
unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;
}
unsigned long long Compute_parity_of_word_with_a_multiply2() {
/*
Also for 64-bits, 8 operations are still enough.
*/
unsigned long long v; // 64-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;
}
unsigned int Compute_parity_in_parallel() {
/*Compute parity in parallel*/
unsigned int v; // word value to compute the parity of
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;
}
void Swapping_values_with_subtraction_and_addition() {
/*Swapping values with subtraction and addition*/
#define SWAP(a, b) ((&(a) == &(b)) || \
(((a) -= (b)), ((b) += (a)), ((a) = (b) - (a))))
}
void Swapping_values_with_XOR() {
/*Swapping values with XOR*/
#define SWAP2(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
}
void Swapping_individual_bits_with_XOR() {
/*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
unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary
r = b ^ ((x << i) | (x << j));
}
void Reverse_bits_the_obvious_way() {
/*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 zero
}
void Reverse_bits_in_word_by_lookup_table() {
/*Reverse bits in word by lookup table*/
static const unsigned char BitReverseTable256[256] =
{
# define R2(n) n, n + 2*64, n + 1*64, n + 3*64
# define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
# define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
R6(0), R6(2), R6(1), R6(3)
};
unsigned int v; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed
//Option 1:
c = (BitReverseTable256[v & 0xff] << 24) |
(BitReverseTable256[(v >> 8) & 0xff] << 16) |
(BitReverseTable256[(v >> 16) & 0xff] << 8) |
(BitReverseTable256[(v >> 24) & 0xff]);
//Option 2:
unsigned char *p = (unsigned char *) &v;
unsigned char *q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]];
q[2] = BitReverseTable256[p[1]];
q[1] = BitReverseTable256[p[2]];
q[0] = BitReverseTable256[p[3]];
}
void Reverse_the_bits_in_a_byte_with_3_operations____64bit_multiply_and_modulus_division___() {
/*Reverse the bits in a byte with 3 operations (64-bit multiply and modulus division):*/
unsigned char b; // reverse this (8-bit) byte
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
}
void Reverse_the_bits_in_a_byte_with_4_operations____64bit_multiply_no_division___() {
/*Reverse the bits in a byte with 4 operations (64-bit multiply, no division):*/
unsigned char b; // reverse this byte
b = ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;
}
void Reverse_the_bits_in_a_byte_with_7_operations____no_64bit___() {
unsigned char b; // reverse this byte
/*Reverse the bits in a byte with 7 operations (no 64-bit):*/
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;
}
void Reverse_an_Nbit_quantity_in_parallel_in_5_times_lg___N____operations() {
/*Reverse an N-bit quantity in parallel in 5 * lg(N) operations:*/
unsigned int v; // 32-bit word to reverse bit order
//swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
//swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
//swap nibbles ...
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
//swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
//swap 2-byte long pairs
v = (v >> 16) | (v << 16);
/*
The following variation is also O(lg(N)), however it requires more
operations to reverse v. Its virtue is in taking less slightly memory
by computing the constants on the fly.
*/
unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;
while ((s >>= 1) > 0) {
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
}
void Compute_modulus_division_by_1_left_shifted_s_without_a_division_operator() {
/*Compute modulus division by 1 << s without a division operator*/
const unsigned int n; // numerator
const unsigned int s;
const unsigned int d = 1U << 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);
}
void Compute_modulus_division_by____1_left_shifted_s_____1_without_a_division_operator() {
/*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 a value from 0 to d, but since with modulus division
//we want m to be 0 when it is d.
m = m == d ? 0 : m;
}
void Compute_modulus_division_by____1_left_shifted_s_____1_in_parallel_without_a_division_operator() {
/*Compute modulus division by (1 << s) - 1 in parallel without a division operator*/
//The following is for a word size of 32 bits!
static const unsigned int M[] =
{
0x00000000, 0x55555555, 0x33333333, 0xc71c71c7,
0x0f0f0f0f, 0xc1f07c1f, 0x3f03f03f, 0xf01fc07f,
0x00ff00ff, 0x07fc01ff, 0x3ff003ff, 0xffc007ff,
0xff000fff, 0xfc001fff, 0xf0003fff, 0xc0007fff,
0x0000ffff, 0x0001ffff, 0x0003ffff, 0x0007ffff,
0x000fffff, 0x001fffff, 0x003fffff, 0x007fffff,
0x00ffffff, 0x01ffffff, 0x03ffffff, 0x07ffffff,
0x0fffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff
};
static const unsigned int Q[][6] =
{
{0, 0, 0, 0, 0, 0},
{16, 8, 4, 2, 1, 1},
{16, 8, 4, 2, 2, 2},
{15, 6, 3, 3, 3, 3},
{16, 8, 4, 4, 4, 4},
{15, 5, 5, 5, 5, 5},
{12, 6, 6, 6, 6, 6},
{14, 7, 7, 7, 7, 7},
{16, 8, 8, 8, 8, 8},
{9, 9, 9, 9, 9, 9},
{10, 10, 10, 10, 10, 10},
{11, 11, 11, 11, 11, 11},
{12, 12, 12, 12, 12, 12},
{13, 13, 13, 13, 13, 13},
{14, 14, 14, 14, 14, 14},
{15, 15, 15, 15, 15, 15},
{16, 16, 16, 16, 16, 16},
{17, 17, 17, 17, 17, 17},
{18, 18, 18, 18, 18, 18},
{19, 19, 19, 19, 19, 19},
{20, 20, 20, 20, 20, 20},
{21, 21, 21, 21, 21, 21},
{22, 22, 22, 22, 22, 22},
{23, 23, 23, 23, 23, 23},
{24, 24, 24, 24, 24, 24},
{25, 25, 25, 25, 25, 25},
{26, 26, 26, 26, 26, 26},
{27, 27, 27, 27, 27, 27},
{28, 28, 28, 28, 28, 28},
{29, 29, 29, 29, 29, 29},
{30, 30, 30, 30, 30, 30},
{31, 31, 31, 31, 31, 31}
};
static const unsigned int R[][6] =
{
{0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000},
{0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000001, 0x00000001},
{0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000003, 0x00000003},
{0x00007fff, 0x0000003f, 0x00000007, 0x00000007, 0x00000007, 0x00000007},
{0x0000ffff, 0x000000ff, 0x0000000f, 0x0000000f, 0x0000000f, 0x0000000f},
{0x00007fff, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f},
{0x00000fff, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f},
{0x00003fff, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f},
{0x0000ffff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff},
{0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff},
{0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff},
{0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff},
{0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff},
{0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff},
{0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff},
{0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff},
{0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff},
{0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff},
{0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff},
{0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff},
{0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff},
{0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff},
{0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff},
{0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff},
{0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff},
{0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff},
{0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff},
{0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff},
{0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff},
{0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff},
{0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff},
{0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff}
};
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.
m = (n & M[s]) + ((n >> s) & M[s]);
for (const unsigned int *q = &Q[s][0], *r = &R[s][0]; m > d; q++, r++) {
m = (m >> *q) + (m & *r);
}
m = m == d ? 0 : m; // OR, less portably: m = m & -((signed)(m - d) >> s);
}
void Find_the_log_base_2_of_an_integer_with_the_MSB_N_set_in_O___N____operations____the_obvious_way___() {
/*Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way)*/
unsigned int v; // 32-bit word to find the log base 2 of
unsigned int r = 0; // r will be lg(v)
while (v >>= 1) // unroll for more speed...
{
r++;
}
}
void Find_the_integer_log_base_2_of_an_integer_with_an_64bit_IEEE_float() {
/*Find the integer log base 2 of an integer with an 64-bit IEEE float*/
int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union {
unsigned int u[2];
double d;
} t; // temp
t.u[__FLOAT_WORD_ORDER == LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER != LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER == LITTLE_ENDIAN] >> 20) - 0x3FF;
}
static const char LogTable256[256] =
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};
void Find_the_log_base_2_of_an_integer_with_a_lookup_table() {
/*Find the log base 2 of an integer with a lookup table*/
unsigned int v; // 32-bit word to find the log of
unsigned r; // r will be lg(v)
register unsigned int t, tt; // temporaries
if (tt = v >> 16) {
r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
} else {
r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}
/*The code above is tuned to uniformly distributed output values. If your inputs are evenly distributed across all 32-bit values, then consider using the following:*/
if (tt = v >> 24) {
r = 24 + LogTable256[tt];
} else if (tt = v >> 16) {
r = 16 + LogTable256[tt];
} else if (tt = v >> 8) {
r = 8 + LogTable256[tt];
} else {
r = LogTable256[v];
}
}
void Find_the_log_base_2_of_an_integer_with_a_lookup_table2() {
/*
To initially generate the log table algorithmically:
*/
// LogTable256[0] = LogTable256[1] = 0; // originally was this
static char LogTable256[256] = {};
for (int i = 2; i < 256; i++) {
LogTable256[i] = 1 + LogTable256[i / 2];
}
LogTable256[0] = -1; // if you want log(0) to return -1
}
void Find_the_log_base_2_of_an_Nbit_integer_in_O___lg___N_______operations() {
/*Find the log base 2 of an N-bit integer in O(lg(N)) operations*/
unsigned int v; // 32-bit value to find the log2 of
const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
const unsigned int S[] = {1, 2, 4, 8, 16};
int i;
register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
if (v & b[i]) {
v >>= S[i];
r |= S[i];
}
}
}
void Find_the_log_base_2_of_an_Nbit_integer_in_O___lg___N_______operations2() {
//OR (IF YOUR CPU BRANCHES SLOWLY):
unsigned int v; // 32-bit value to find the log2 of
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;
r = (v > 0xFFFF) << 4;
v >>= r;
shift = (v > 0xFF) << 3;
v >>= shift;
r |= shift;
shift = (v > 0xF) << 2;
v >>= shift;
r |= shift;
shift = (v > 0x3) << 1;
v >>= shift;
r |= shift;
r |= (v >> 1);
}
void Find_the_log_base_2_of_an_Nbit_integer_in_O___lg___N_______operations3() {
//OR (IF YOU KNOW v IS A POWER OF 2):
int i;
unsigned int v; // 32-bit value to find the log2 of
static const unsigned int b[] = {0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0,
0xFF00FF00, 0xFFFF0000};
register unsigned int r = (v & b[0]) != 0;
for (i = 4; i > 0; i--) // unroll for speed...
{
r |= ((v & b[i]) != 0) << i;
}
}
int Find_the_log_base_2_of_an_Nbit_integer_in_O___lg___N_______operations_with_multiply_and_lookup(uint32_t v) {
/*Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup*/
//uint32_t v; // find the log base 2 of 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
r = MultiplyDeBruijnBitPosition[(uint32_t) (v * 0x07C4ACDDU) >> 27];
/*If you know that v is a power of 2, then you only need the following:*/
static const int MultiplyDeBruijnBitPosition2[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition2[(uint32_t) (v * 0x077CB531U) >> 27];
return r;
}
void Find_integer_log_base_10_of_an_integer() {
/*Find integer log base 10 of an integer*/
unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of
int r; // result goes here
int t; // temporary
static unsigned int const PowersOf10[] =
{1, 10, 100, 1000, 10000, 100000,
1000000, 10000000, 100000000, 1000000000};
v = (unsigned int) Find_the_log_base_2_of_an_Nbit_integer_in_O___lg___N_______operations_with_multiply_and_lookup(
v);
// t = (IntegerLogBase2(v) + 1) * 1233 >> 12; // (use a lg2 method from above) note: this was originally this
t = (v + 1) * 1233 >> 12; // (use a lg2 method from above)
r = t - (v < PowersOf10[t]);
}
void Find_integer_log_base_10_of_an_integer_the_obvious_way() {
/*Find integer log base 10 of an integer the obvious way*/
unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of
int r; // result goes here
r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 :
(v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 :
(v >= 1000) ? 3 : (v >=
100)
? 2
: (v >=
10)
? 1
: 0;
}
void Find_integer_log_base_2_of_a_32bit_IEEE_float() {
/*Find integer log base 2 of a 32-bit IEEE float*/
const float v; // find int(log2(v)), where v > 0.0 && finite(v) && isnormal(v)
int c; // 32-bit int c gets the result;
c = *(const int *) &v; // OR, for portability: memcpy(&c, &v, sizeof c);
c = (c >> 23) - 127;
}
void Find_integer_log_base_2_of_a_32bit_IEEE_float2() {
/*)
The above is fast, but IEEE 754-compliant architectures utilize subnormal (also called denormal) floating point numbers.
These have the exponent bits set to zero (signifying pow(2,-127)),
and the mantissa is not normalized, so it contains leading zeros and
thus the log2 must be computed from the mantissa. To accommodate for
subnormal numbers, use the following:
*/
const float v; // find int(log2(v)), where v > 0.0 && finite(v)
int c; // 32-bit int c gets the result;
int x = *(const int *) &v; // OR, for portability: memcpy(&x, &v, sizeof x);
c = x >> 23;
if (c) {
c -= 127;
} else { // subnormal, so recompute using mantissa: c = intlog2(x) - 149;
register unsigned int t; // temporary
// Note that LogTable256 was defined earlier
if (t = x >> 16) {
c = LogTable256[t] - 133;
} else {
c = (t = x >> 8) ? LogTable256[t] - 141 : LogTable256[x] - 149;
}
}
}
void Find_integer_log_base_2_of_the_pow___2_r___root_of_a_32bit_IEEE_float____for_unsigned_integer_r___() {
/*Find integer log base 2 of the pow(2, r)-root of a 32-bit IEEE float (for unsigned integer r)*/
const int r;
const float v; // find int(log2(pow((double) v, 1. / pow(2, r)))),
// where isnormal(v) and v > 0
int c; // 32-bit int c gets the result;
c = *(const int *) &v; // OR, for portability: memcpy(&c, &v, sizeof c);
c = ((((c - 0x3f800000) >> r) + 0x3f800000) >> 23) - 127;
}
void Count_the_consecutive_zero_bits____trailing____on_the_right_linearly() {
/*Count the consecutive zero bits (trailing) on the right linearly*/
unsigned int v; // input to count trailing zero bits
int c; // output: c will count v's trailing zero bits,
// so if v is 1101000 (base 2), then c will be 3
if (v) {
v = (v ^ (v - 1)) >> 1; // Set v's trailing 0s to 1s and zero rest
for (c = 0; v; c++) {
v >>= 1;
}
} else {
c = CHAR_BIT * sizeof(v);
}
}
void Count_the_consecutive_zero_bits____trailing____on_the_right_in_parallel() {
/*Count the consecutive zero bits (trailing) on the right in parallel*/
unsigned int v; // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
int vsigned = (int) v;
v &= -vsigned;
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;
}
void Count_the_consecutive_zero_bits____trailing____on_the_right_by_binary_search() {
/*Count the consecutive zero bits (trailing) on the right by binary search*/
unsigned int v; // 32-bit word input to count zero bits on right
unsigned int c; // c will be the number of zero bits on the right,
// so if v is 1101000 (base 2), then c will be 3
//NOTE: if 0 == v, then c = 31.
if (v & 0x1) {
// special case for odd v (assumed to happen half of the time)
c = 0;
} else {
c = 1;
if ((v & 0xffff) == 0) {
v >>= 16;
c += 16;
}
if ((v & 0xff) == 0) {
v >>= 8;
c += 8;
}
if ((v & 0xf) == 0) {
v >>= 4;
c += 4;
}
if ((v & 0x3) == 0) {
v >>= 2;
c += 2;
}
c -= v & 0x1;
}
}
void Count_the_consecutive_zero_bits____trailing____on_the_right_by_casting_to_a_float() {
/*Count the consecutive zero bits (trailing) on the right by casting to a float*/
unsigned int v; // find the number of trailing zeros in v
int r; // the result goes here
float f = (float) (v & -v); // cast the least significant bit in v to a float
r = (*(uint32_t *) &f >> 23) - 0x7f;
}
void Count_the_consecutive_zero_bits____trailing____on_the_right_with_modulus_division_and_lookup() {
/*Count the consecutive zero bits (trailing) on the right with modulus division and lookup*/
unsigned int v; // find the number of trailing zeros in v
int r; // put the result in r
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
20, 8, 19, 18
};
r = Mod37BitPosition[(-v & v) % 37];
}
void Count_the_consecutive_zero_bits____trailing____on_the_right_with_multiply_and_lookup() {
/*Count the consecutive zero bits (trailing) on the right with multiply and lookup*/
unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t) ((v & -v) * 0x077CB531U)) >> 27];
}
void Round_up_to_the_next_highest_power_of_2_by_float_casting() {
/*Round up to the next highest power of 2 by float casting*/
unsigned int const v; // Round this 32-bit value to the next highest power of 2
unsigned int r; // Put the result here. (So v=3 -> r=4; v=8 -> r=8)
if (v > 1) {
float f = (float) v;
unsigned int const t = 1U << ((*(unsigned int *) &f >> 23) - 0x7f);
r = t << (t < v);
} else {
r = 1;
}
/*Quick and dirty version, for domain of 1 < v < (1<<25):*/
float f = (float) (v - 1);
r = 1U << ((*(unsigned int *) (&f) >> 23) - 126);
}
void Round_up_to_the_next_highest_power_of_2() {
/*Round up to the next highest power of 2*/
unsigned int v; // compute the next highest power of 2 of 32-bit v
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
}
void Interleave_bits_the_obvious_way() {
/*Interleave bits the obvious way*/
unsigned short x; // Interleave bits of x and y, so that all of the
unsigned short y; // bits of x are in the even positions and y in the odd;
unsigned int z = 0; // z gets the resulting Morton Number.
for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed...
{
z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1);
}
}
void Interleave_bits_by_table_lookup() {
/*Interleave bits by table lookup*/
static const unsigned short MortonTable256[256] =
{
0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
};
unsigned short x; // Interleave bits of x and y, so that all of the
unsigned short y; // bits of x are in the even positions and y in the odd;
unsigned int z; // z gets the resulting 32-bit Morton Number.
z = MortonTable256[y >> 8] << 17 |
MortonTable256[x >> 8] << 16 |
MortonTable256[y & 0xFF] << 1 |
MortonTable256[x & 0xFF];
}
void Interleave_bits_with_64bit_multiply() {
/*
In 11 operations, this version interleaves bits of two bytes
(rather than shorts, as in the other versions),
but many of the operations are 64-bit multiplies
so it isn't appropriate for all machines. The input parameters, x and y,
should be less than 256.
*/
unsigned char x; // Interleave bits of (8-bit) x and y, so that all of the
unsigned char y; // bits of x are in the even positions and y in the odd;
unsigned short z; // z gets the resulting 16-bit Morton Number.
z = ((x * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 49) & 0x5555 |
((y * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 48) & 0xAAAA;
}
void Interleave_bits_by_Binary_Magic_Numbers() {
/*Interleave bits by Binary Magic Numbers*/
static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
static const unsigned int S[] = {1, 2, 4, 8};
unsigned int x; // Interleave lower 16 bits of x and y, so the bits of x
unsigned int y; // are in the even positions and bits from y in the odd;
unsigned int z; // z gets the resulting 32-bit Morton Number.
// x and y must initially be less than 65536.
x = (x | (x << S[3])) & B[3];
x = (x | (x << S[2])) & B[2];
x = (x | (x << S[1])) & B[1];
x = (x | (x << S[0])) & B[0];
y = (y | (y << S[3])) & B[3];
y = (y | (y << S[2])) & B[2];
y = (y | (y << S[1])) & B[1];
y = (y | (y << S[0])) & B[0];
z = x | (y << 1);
}
void Determine_if_a_word_has_a_zero_byte() {
/*Determine if a word has a zero byte*/
//Fewer operations:
unsigned int v; // 32-bit word to check if any 8-bit byte in it is 0
bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);
/*
The code above may be useful when doing a fast string copy in which a word
is copied at a time; it uses 5 operations.
On the other hand, testing for a null byte in the obvious ways (which follow)
have at least 7 operations (when counted in the most sparing way), and at most 12.
*/
//More operations:
bool hasNoZeroByte = ((v & 0xff) && (v & 0xff00) && (v & 0xff0000) && (v & 0xff000000));
}
void Determine_if_a_word_has_a_zero_byte2() {
//OR:
unsigned int v; // 32-bit word to check if any 8-bit byte in it is 0
unsigned char *p = (unsigned char *) &v;
bool hasNoZeroByte = *p && *(p + 1) && *(p + 2) && *(p + 3);
/*
*/
bool hasZeroByte = ((v + 0x7efefeff) ^ ~v) & 0x81010100;
if (hasZeroByte) // or may just have 0x80 in the high byte
{
hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);
}
/*There is yet a faster method — use hasless(v, 1), which is defined below; it works in 4 operations and requires no subsquent verification. It simplifies to*/
#define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL)
}
void Determine_if_a_word_has_a_byte_equal_to_n() {
/*.
*/
#define hasvalue(x, n) \
(haszero((x) ^ (~0UL/255 * (n))))
}
void Determine_if_a_word_has_a_byte_less_than_n() {
/*Requirements: x>=0; 0<=n<=128*/
#define hasless(x, n) (((x)-~0UL/255*(n))&~(x)&~0UL/255*128)
/*
To count the number of bytes in x that are less than n in 7 operations, use
*/
#define countless(x, n) \
(((~0UL/255*(127+(n))-((x)&~0UL/255*127))&~(x)&~0UL/255*128)/128%255)
}
void Determine_if_a_word_has_a_byte_greater_than_n() {
/*Requirements: x>=0; 0<=n<=127*/
#define hasmore(x, n) (((x)+~0UL/255*(127-(n))|(x))&~0UL/255*128)
/*
To count the number of bytes in x that are more than n in 6 operations, use:
*/
#define countmore(x, n) \
(((((x)&~0UL/255*127)+~0UL/255*(127-(n))|(x))&~0UL/255*128)/128%255)
}
void Determine_if_a_word_has_a_byte_between_m_and_n() {
/*
*/
#define likelyhasbetween(x, m, n) \
((((x)-~0UL/255*(n))&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)
/*
This technique would be suitable for a fast pretest. A variation that
takes one more operation (8 total for constant m and n)
but provides the exact answer is:
*/
#define hasbetween(x, m, n) \
((~0UL/255*(127+(n))-((x)&~0UL/255*127)&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)
/*
To count the number of bytes in x that are between m and n (exclusive)
in 10 operations, use:
*/
#define countbetween(x, m, n) (hasbetween(x,m,n)/128%255)
}
void Compute_the_lexicographically_next_bit_permutation() {
/*
Suppose we have a pattern of N bits set to 1 in an integer and we want the
next permutation of N 1 bits in a lexicographical sense.
For example, if N is 3 and the bit pattern is 00010011, the next patterns
would be 00010101, 00010110, 00011001,00011010, 00011100, 00100011,
and so forth. The following is a fast way to compute the next permutation.
*/
unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits
unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
//Next set to 1 the most significant bit to change,
//set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
}
void Compute_the_lexicographically_next_bit_permutation2() {
unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits
/*Here is another version that tends to be slower because of its division operator, but it does not require counting the trailing zeros.*/
unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment