/************************************************************************* Class : BITMANI Component : Utilities -------------------------------------------------------------------------- short description: The module bitmani provides a container class with functions to manipulate bits within integers. The functions are inlined (=>no debugging). Shift operations ( << and >> ) are undefined in C++ (Stroustrup, r.5.8) if the right argument is negative or >= size of left argument. Hence shift operations without an upper bound are provided plus a function Shift useful for negative shifts. There are three types of functions in this class. First there are functions with an O(1) running time. Functions of this class are independent of the size of type integer. Second there are functions with an O(log(number of bits of an integer)) running time. Functions of this class only work for this number of bits. Functions of this class are: Count, Gray2I, Parity, Lowest, Highest, and Reverse. Third there are functions with an O(number of bits of an integer) running time. Functions of this type typically contain a loop over all bits or chunk of bits. Functions of this class are: CounT Note: Count is faster than CounT if the number of bits is 64 or more. An exceptional function is CountSparse whose running time depends on the arguments. Limitation: Most functions assume that the number of bits for an unsigned int is 32. If this class should be used for 64 bit integers some extra lines of code have to be inserted. These are: CountT, Count, Gray2I, Parity, Lowest, Highest, and Swap16. Two new functions Swap32 and Reverse64 (= Reverse) had to be added. Exported functions: ------------------- Number of 1-Bits: static int CounT( unsigned int w ) static int Count( unsigned int w ) static int CountSparse( unsigned int w ) Change from and to Graycode: static unsigned int I2Gray (unsigned int w) static unsigned int Gray2I (unsigned int w) Recognition of certain bit patterns: static unsigned int Parity (unsigned int w) static bool OneBit (unsigned int w) // power of two static bool IsBlock (unsigned int w) static bool IsHighBlock (unsigned int w) static bool IsLowBlock (unsigned int w) static bool Subset (unsigned int u, unsigned int v) Check, set, delete or change a bit: static bool Test (unsigned int w, unsigned int pos) static unsigned int Set (unsigned int w, unsigned int pos) static unsigned int Reset (unsigned int w, unsigned int pos) static unsigned int Change (unsigned int w, unsigned int pos) Swap two bits: static unsigned int Exchange (unsigned int w, unsigned int pos1, unsigned int pos2) Determine the position of highest or lowest bit: static int Highest (unsigned int w) static int Lowest (unsigned int w) static unsigned int LowestBit (unsigned int w) Shift or rotate a bit: static unsigned int Shift (unsigned int w, int s) static unsigned int RightShift (unsigned int w, unsigned int s) static unsigned int LeftShift (unsigned int w, unsigned int s) static unsigned int Rotate (unsigned int w, int s) static unsigned int RightRotate (unsigned int w, unsigned int s) static unsigned int LeftRotate (unsigned int w, unsigned int s) Swap or reverse blocks of bits: static unsigned int Swap16 (unsigned int u) static unsigned int Swap8 (unsigned int u) static unsigned int Swap4 (unsigned int u) static unsigned int Swap2 (unsigned int u) static unsigned int Swap1 (unsigned int u) static unsigned int Reverse32 (unsigned int u) static unsigned int Reverse16 (unsigned int u) static unsigned int Reverse8 (unsigned int u) static unsigned int Reverse4 (unsigned int u) static unsigned int Reverse2 (unsigned int u) Merging: static unsigned int Butterfly1 (unsigned int w) static unsigned int Butterfly2 (unsigned int w) static unsigned int Butterfly4 (unsigned int w) static unsigned int Butterfly8 (unsigned int w) The butterfly step is the swap A B C D | \ / | | X | | / \ | A C B D Generating the next combination: static unsigned int NextComb (unsigned int w) This module needs no initialisation. A short description how to create periodical bit masks, if the width is a power of two. (All numbers are binary!). Only 1s : A1 = 111...1111111 = ~0U period 2 : A2 = ...0101010101 = A1 / 11 period 4 : A4 = ...1100110011 = A1 / 101 period 8 : A8 = ...1100001111 = A1 / 10001 The period must be a divisor of the width. -------------------------------------------------------------------------- Author: Torsten Sillke, LH-Systems, 1994 Last Update: 2000-08-30 mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/ALGORITHMS/ *************************************************************************/ // #ifndef BITMANI_INCLUDED #define BITMANI_INCLUDED //------------------------ Header ------------------------------------------ //------------------------ Defines ----------------------------------------- #define BITMANI_RIGHT_SHIFT_BOUND_CHECK_NECESSARY 1 #define BITMANI_LEFT_SHIFT_BOUND_CHECK_NECESSARY 1 // ANSI behavior is: // #define BITMANI_RIGHT_SHIFT_BOUND_CHECK_NECESSARY 1 // #define BITMANI_LEFT_SHIFT_BOUND_CHECK_NECESSARY 1 // Other settings are optimizations for a specific compiler. // This can't be computed by preprocessor, because shifts of constant // shift width >= 32 are yielding always 0 (correct behavior). //------------------------ Class ------------------------------------------- class BITMANI { private: // Membervariables static const int b11[2048]; // The array b11 contains for every byte the number of 1-bits (filled in .c). // This array is only used in function CounT(). public: enum { nof = 32 }; // (number of bits in int) // /********************************************************************* NAME : CounT INPUT : unsigned int w RESULT : int EFFECT : computation of 1-bits in an unsigned int. ---------------------------------------------------------------------- This method is table driven. This table is set in the c-file. **********************************************************************/ static int CounT (unsigned int w) { return b11[w & 0x7ff] + b11[(w>>11) & 0x7ff] + b11[(w>>22)]; } /********************************************************************* NAME : Count INPUT : unsigned int w RESULT : int EFFECT : computation of 1-bits in an unsigned int. ---------------------------------------------------------------------- Algorithm: - Edward M. Reingold, Jurg Nievergelt, and Narsingh Deo, "Combinatorial algorithms - theory and practice" Prentice-Hall, Englewood Cliffs, 1977. (ISBN 0-13-152447-X) pages 2-6 - Jon Bentley, "Programming Pearls", 1st ed., p 173 - Paeth, Alan W., and Schilling, David, Of Integers, Fields, and Bit Counting, p. 371-376, code: p. 610-611, in: Graphics Gems II, James Arvo (editor), Academic Press, 1991, ISBN: 0120644819. http://www.graphicsgems.org/ - ftp://38.168.214.175/pub/bitcount/BITC.ZIP int Count (unsigned int w) { // binary technique for 32 bit words w = (0x55555555 & w) + (0x55555555 & (w>> 1)); w = (0x33333333 & w) + (0x33333333 & (w>> 2)); w = (0x0f0f0f0f & w) + (0x0f0f0f0f & (w>> 4)); w = (0x00ff00ff & w) + (0x00ff00ff & (w>> 8)); w = (0x0000ffff & w) + (0x0000ffff & (w>>16)); return w; } This already reuses the bitmasks which are expensive, but further optimizations have been done in the code below. **********************************************************************/ static int Count (unsigned int w) { // binary technique for 2**n bit words with n=5. const unsigned int mask1h = (~0U) / 3 << 1; const unsigned int mask2l = (~0U) / 5; const unsigned int mask4l = (~0U) / 17; w -= (mask1h & w) >> 1; w = (w & mask2l) + ((w>>2) & mask2l); w += w >> 4; // 8 bit fold. w &= mask4l; // set width=8. w += w >> 8; // 16 bit fold. w += w >> 16; // 32 bit fold. // w += w >> 32; // 64 bit fold. // w += w >> 64; // 128 bit fold. return w & 0xff; // select 8 bits. (4<=n<8) } // /********************************************************************* NAME : CountSparse INPUT : unsigned int w RESULT : int EFFECT : computation of 1-bits in an unsigned int. ---------------------------------------------------------------------- Fast if only very few bits are set on the average. Each cycle counts and deletes the smallest set bit. This algorithm is a problem assignment in K&R, Excercise 2-9. Using unsigned integers makes no assumption on 1- or 2-complement representation of the integers. **********************************************************************/ static int CountSparse (unsigned int w) { int n = 0; if ( w ) do ++n; while ( w &= w-1 ); return n; } // /********************************************************************* NAME : I2Gray INPUT : unsigned int lexical RESULT : unsigned int GrayCode EFFECT : lexicographical order -> GrayCode ---------------------------------------------------------------------- Some bits may change in lexicographical order for i -> i+1. The gray code changes only one bit. int: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 binary: 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 Gray: 0 1 11 10 110 111 101 100 1100 1101 1111 1110 1010 1011 1001 1000 **********************************************************************/ static unsigned int I2Gray (unsigned int w) { // converting: unsigned int -> gray code return w ^ (w>>1); } /********************************************************************* NAME : Gray2I INPUT : unsigned int GrayCode RESULT : unsigned int lexical EFFECT : lexicographical order -> GrayCode ---------------------------------------------------------------------- int: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 binary: 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 Gray: 0 1 11 10 110 111 101 100 1100 1101 1111 1110 1010 1011 1001 1000 **********************************************************************/ static unsigned int Gray2I (unsigned int w) { // converting: gray code -> unsigned int // implementation for 32 bit words w ^= w>>1; w ^= w>>2; w ^= w>>4; w ^= w>>8; w ^= w>>16; return w; } // /********************************************************************* NAME : Parity INPUT : unsigned int w RESULT : unsigned int EFFECT : parity of the number of 1-bits. (number % 2) ---------------------------------------------------------------------- **********************************************************************/ static unsigned int Parity (unsigned int w) { // parity of the number of 1-bit // 0 if even; 1 if odd // implementation for 32 bit words w ^= w>>1; w ^= w>>2; w ^= w>>4; w ^= w>>8; w ^= w>>16; return w & 1; } /********************************************************************* NAME : OneBit INPUT : unsigned int w RESULT : bool EFFECT : check for one bit exactly set Pattern 0* 1 0* ---------------------------------------------------------------------- **********************************************************************/ static bool OneBit (unsigned int w) { unsigned wm = w-1; return (w ^ wm) >> 1 == wm; } /********************************************************************* NAME : IsBlock INPUT : unsigned int w RESULT : bool EFFECT : check wether all 1-bits are in line Pattern 0* 1* 0* ---------------------------------------------------------------------- examples : 00000000, 00000111, 11110000, 00111000 ->1 01010101, 11100111, 00000101, 00101000 -> 0 **********************************************************************/ static bool IsBlock (unsigned int w) { unsigned wm = w|w-1; w = wm+1; return (w ^ wm) + 1 == w+w; } /********************************************************************* NAME : IsHighBlock INPUT : unsigned int w RESULT : bool EFFECT : check wether there's no pair 01 Pattern 1* 0* ---------------------------------------------------------------------- **********************************************************************/ static bool IsHighBlock (unsigned int w) { return !~(w | w-1); } /********************************************************************* NAME : IsLowBlock INPUT : unsigned int w RESULT : bool EFFECT : check wether there's no pair 10 Pattern 0* 1* ---------------------------------------------------------------------- **********************************************************************/ static bool IsLowBlock (unsigned int w) { w = ~w; return !~(w | w-1); } // /********************************************************************* NAME : Test INPUT : unsigned int w unsigned int pos RESULT : bool EFFECT : check bit on position pos ---------------------------------------------------------------------- **********************************************************************/ static bool Test (unsigned int w, unsigned int pos) { return (w & LeftShift(1, pos)) > 0; } /********************************************************************* NAME : Set INPUT : unsigned int w unsigned int pos RESULT : unsigned int EFFECT : sets bit at position pos in w ---------------------------------------------------------------------- **********************************************************************/ static unsigned int Set (unsigned int w, unsigned int pos) { return w |= LeftShift(1, pos); } /********************************************************************* NAME : Reset INPUT : unsigned int w unsigned int pos RESULT : unsigned int EFFECT : deletes bit at position pos in w ---------------------------------------------------------------------- **********************************************************************/ static unsigned int Reset (unsigned int w, unsigned int pos) { return w &= ~LeftShift(1, pos); } /********************************************************************* NAME : Change INPUT : unsigned int w unsigned int pos RESULT : unsigned int EFFECT : inverts bit at position pos in w ---------------------------------------------------------------------- **********************************************************************/ static unsigned int Change (unsigned int w, unsigned int pos) { return w ^= LeftShift(1, pos); } /********************************************************************* NAME : Exchange INPUT : unsigned int w unsigned int pos1 unsigned int pos2 RESULT : unsigned int EFFECT : swaps bits at position pos1, pos2 in w: pos1 <-> pos2 ---------------------------------------------------------------------- bits at positions >= nof are treated as 0 **********************************************************************/ static unsigned int Exchange (unsigned int w, unsigned int pos1, unsigned int pos2) { unsigned int m1 = LeftShift(1, pos1); unsigned int m2 = LeftShift(1, pos2); // Bits must only be treated if the are different. // Then they are to be inverted. if (!(w & m1) != !(w & m2)) w ^= m1 | m2; return w; } // /********************************************************************* NAME : Highest INPUT : unsigned int w RESULT : int EFFECT : gives position of the highest bit=1 (numbering starts with 0) (w==0 -> -1) ---------------------------------------------------------------------- **********************************************************************/ static int Highest (unsigned int w) { // binary Search (Assembly Language Ref. Man. Example 1) // implementation for 32 bit words int pos = 0; if (w) { if (w & 0xffff0000) { w >>= 16; pos += 16; } if (w & 0x0000ff00) { w >>= 8; pos += 8; } if (w & 0x000000f0) { w >>= 4; pos += 4; } if (w & 0x0000000c) { w >>= 2; pos += 2; } if (w & 0x00000002) { pos += 1; } } else pos = -1; return pos; } /********************************************************************* NAME : Lowest INPUT : unsigned int w RESULT : int EFFECT : gives position of the lowest bit=1 (numbering starts with 0) (w==0 -> -1) ---------------------------------------------------------------------- This function exists in as 'ffs'. (numbering starts with 1, ffs(0) = 0). (ffs ~ F(ind) F(irst) (bit) S(et)) The function is implemented with a loop. **********************************************************************/ static int Lowest (unsigned int w) { // binary Search (HP Assembly Language Ref. Man. Example 1) // implemantation for 32 bit words int pos = 0; if (w) { if (!(w & 0x0000ffff)) { w >>= 16; pos += 16; } if (!(w & 0x000000ff)) { w >>= 8; pos += 8; } if (!(w & 0x0000000f)) { w >>= 4; pos += 4; } if (!(w & 0x00000003)) { w >>= 2; pos += 2; } if (!(w & 0x00000001)) { pos += 1; } } else pos = -1; return pos; } /********************************************************************* NAME : LowestBit INPUT : unsigned int w RESULT : unsigned int EFFECT : gives bitmask with the lowest bit=1 For 0 a 0 is returned. ---------------------------------------------------------------------- **********************************************************************/ static unsigned int LowestBit (unsigned int w) { if (w==0) return 0; return ((w ^ (w-1))>>1)+1; } // /********************************************************************* NAME : Shift INPUT : unsigned int w int s RESULT : unsigned int EFFECT : the word w is shifted by s (s negative shifts to the right.) ---------------------------------------------------------------------- result = w * 2^s Shifts << or >> are undefined in C++ (Stroustrup, r.5.8), if the right argument is negative or >= length of left argument. **********************************************************************/ static unsigned int Shift (unsigned int w, int s) { unsigned int res = 0; if (s >= 0) res = LeftShift( w, s ); else res = RightShift( w, s ); return res; } /********************************************************************* NAME : RightShift INPUT : unsigned int w unsigned int s RESULT : unsigned int EFFECT : the word w is shifted by s to the right ---------------------------------------------------------------------- all s >= 0 are allowed. **********************************************************************/ static unsigned int RightShift (unsigned int w, unsigned int s) { // ANSI-C(++) needs checking the bound #if BITMANI_RIGHT_SHIFT_BOUND_CHECK_NECESSARY if (s >= nof) w=0; #endif return w >> s; } /********************************************************************* NAME : LeftShift INPUT : unsigned int w unsigned int s RESULT : unsigned int EFFECT : the word w is shifted to the left by s. ---------------------------------------------------------------------- all s >= 0 are allowed. **********************************************************************/ static unsigned int LeftShift (unsigned int w, unsigned int s) { // ANSI-C(++) needs checking the bound #if BITMANI_LEFT_SHIFT_BOUND_CHECK_NECESSARY if (s >= nof) w=0; #endif return w << s; } // /********************************************************************* NAME : Rotate INPUT : unsigned int w int s RESULT : unsigned int EFFECT : the word w is rotated by s to the left. (s negative rotates to the right) ---------------------------------------------------------------------- **********************************************************************/ static unsigned int Rotate (unsigned int w, int s) { if (s>=0) s = (nof-s) & (nof-1); else s = (-s) & (nof-1); // '>>' only with shift 0<=s<=nof-1 #if BITMANI_LEFT_SHIFT_BOUND_CHECK_NECESSARY return ((w+w) << nof-1-s) | (w >> s); #else return (w << nof-s) | (w >> s); #endif } // /********************************************************************* NAME : RightRotate INPUT : unsigned int w unsigned int s RESULT : unsigned int EFFECT : the word w is rotated by s to the right. ---------------------------------------------------------------------- **********************************************************************/ static unsigned int RightRotate (unsigned int w, unsigned int s) { s = s & (nof-1); // nof must be a power of two. // '>>' only with shift 0<=s<=nof-1 #if BITMANI_LEFT_SHIFT_BOUND_CHECK_NECESSARY return (s==0) ? w : (w << nof-s) | (w >> s); #else return (w << nof-s) | (w >> s); #endif } /********************************************************************* NAME : LeftRotate INPUT : unsigned int w unsigned int s RESULT : unsigned int EFFECT : the word w is rotated by s to the left. ---------------------------------------------------------------------- **********************************************************************/ static unsigned int LeftRotate (unsigned int w, unsigned int s) { s = (nof-s) & (nof-1); // nof must be a power of two. // '>>' only with shift 0<=s<=nof-1 #if BITMANI_LEFT_SHIFT_BOUND_CHECK_NECESSARY return (s == 0) ? w : (w << nof-s) | (w >> s); #else return (w << nof-s) | (w >> s); #endif } // /********************************************************************* NAME : Subset INPUT : unsigned int u unsigned int v RESULT : bool EFFECT : check wether each 1-bit of u is also 1-bit of v. ---------------------------------------------------------------------- **********************************************************************/ static bool Subset (unsigned int u, unsigned int v) { return (u & v) == u; } // /********************************************************************* NAME : Swap16 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps the upper and lower 16-bit block ---------------------------------------------------------------------- Swap16(u) == RightRotate(u,16) == LeftRotate(u,16) Swap8(0x12345678) -> 0x56781234 **********************************************************************/ static unsigned int Swap16 (unsigned int w) { // unsigned int m = (~0U) / 0x10001; // 0x0000ffff; // return ((w & m) << 16) | ((w >> 16) & m); // 32 bit version return (w << 16) | (w >> 16); } /********************************************************************* NAME : Swap8 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps pairs of 8-bit blocks ---------------------------------------------------------------------- Swap8(0x12345678) -> 0x34127856 **********************************************************************/ static unsigned int Swap8 (unsigned int w) { unsigned int m = (~0U) / 0x101; // 0x00ff00ff; return ((w & m) << 8) | ((w >> 8) & m); } /********************************************************************* NAME : Swap4 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps pairs of 4-bit blocks ---------------------------------------------------------------------- Swap4(0x12345678) -> 0x21436587 **********************************************************************/ static unsigned int Swap4 (unsigned int w) { unsigned int m = (~0U) / 0x11; // 0x0f0f0f0f; return ((w & m) << 4) | ((w >> 4) & m); } /********************************************************************* NAME : Swap2 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps pairs of 2-bit blocks ---------------------------------------------------------------------- Swap2(0x12345678) -> 0x48c159d2 (Binaer: ABcd -> cdAB) **********************************************************************/ static unsigned int Swap2 (unsigned int w) { unsigned int m = (~0U) / 0x5; // 0x33333333; return ((w & m) << 2) | ((w >> 2) & m); } /********************************************************************* NAME : Swap1 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps pairs of 1-bit blocks ---------------------------------------------------------------------- Swap1(0x12345678) -> 0x2138a9b4 (binary: AbCd -> bAdC) **********************************************************************/ static unsigned int Swap1 (unsigned int w) { unsigned int m = (~0U) / 0x3; // 0x55555555; return ((w & m) << 1) | ((w >> 1) & m); } // /********************************************************************* NAME : Reverse2 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps the bit order of each 2-bit block ---------------------------------------------------------------------- Swap1(u) == Reverse2(u) Reverse2(0x12345678) -> 0x2138a9b4 (Binaer: AbCd -> bAdC) **********************************************************************/ static unsigned int Reverse2 (unsigned int w) { unsigned int m = (~0U) / 0x3; // 0x55555555; return ((w & m) << 1) | ((w >> 1) & m); } /********************************************************************* NAME : Reverse4 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps the bit order of each 4-bit block ---------------------------------------------------------------------- Reverse4(0x12345678) -> 0x84c2a6e1 **********************************************************************/ static unsigned int Reverse4 (unsigned int u) { return Reverse2( Swap2(u) ); } /********************************************************************* NAME : Reverse8 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps the bit order of each 8-bit block ---------------------------------------------------------------------- **********************************************************************/ static unsigned int Reverse8 (unsigned int u) { return Reverse4( Swap4(u) ); } /********************************************************************* NAME : Reverse16 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps the bit order of each 16-bit block ---------------------------------------------------------------------- **********************************************************************/ static unsigned int Reverse16 (unsigned int u) { return Reverse8( Swap8(u) ); } /********************************************************************* NAME : Reverse32 INPUT : unsigned int u RESULT : unsigned int EFFECT : swaps the bit order in unsigned (32 bit) ---------------------------------------------------------------------- **********************************************************************/ static unsigned int Reverse32 (unsigned int u) { return Reverse16( Swap16(u) ); } // /********************************************************************* NAME : Butterfly1 INPUT : unsigned int u RESULT : unsigned int EFFECT : butterfly of 1-bit blocks ---------------------------------------------------------------------- Butterfly1(0x12345678) -> 0x14523678 **********************************************************************/ static unsigned int Butterfly1 (unsigned int w) { unsigned int m = 0x22222222; return ((w & m) << 1) | ((w >> 1) & m) | (w & ~(3*m)); } /********************************************************************* NAME : Butterfly2 INPUT : unsigned int u RESULT : unsigned int EFFECT : butterfly of 2-bit blocks ---------------------------------------------------------------------- Butterfly2(0x12345678) -> 0x061c566c **********************************************************************/ static unsigned int Butterfly2 (unsigned int w) { unsigned int m = 0x0c0c0c0c; return ((w & m) << 2) | ((w >> 2) & m) | (w & ~(5*m)); } /********************************************************************* NAME : Butterfly4 INPUT : unsigned int u RESULT : unsigned int EFFECT : butterfly of 4-bit blocks ---------------------------------------------------------------------- Butterfly4(0x12345678) -> 0x13245768 **********************************************************************/ static unsigned int Butterfly4 (unsigned int w) { unsigned int m = 0x00f000f0; return ((w & m) << 4) | ((w >> 4) & m) | (w & ~(0x11*m)); } /********************************************************************* NAME : Butterfly8 INPUT : unsigned int u RESULT : unsigned int EFFECT : butterfly of 8-bit blocks ---------------------------------------------------------------------- Butterfly8(0x12345678) -> 0x12563478 **********************************************************************/ static unsigned int Butterfly8 (unsigned int w) { unsigned int m = 0x0000ff00; return ((w & m) << 8) | ((w >> 8) & m) | (w & ~(0x101*m)); } // /********************************************************************* NAME : NextComb INPUT : unsigned int u RESULT : unsigned int EFFECT : Smallest integer greater than u with the same number of bits set. ---------------------------------------------------------------------- Examples (binary notation): 1 -> 10 -> 100 -> 1000 -> 10000 -> 100000 -> 1000000 -> ... 11 -> 101 -> 110 -> 1001 -> 1010 -> 1100 -> 10001 -> ... 111 -> 1011 -> 1101 -> 1110 -> 10011 -> 10101 -> 10110 -> ... Special cases: 0 -> 0 if the number is too large then 0 is returned. The bit pattern to change at the end of the word is: 0 1 0 -> 1 0 1 a b b+1 a-1 Example: (the bits marked by B remain fixed) w = BBBB01111100000000 z = 000000000100000000 (the lowest set bit) w+z = BBBB10000000000000 (w+z)^w = 000011111100000000 Next = BBBB10000000001111 Reference: HAKMEM Item 175 In two's compelment arithmetic: z = w & -w; **********************************************************************/ static unsigned int NextComb (unsigned int w) { unsigned int ww = w, z; if (ww) { z = w & -w; w += z; if (w) w += (w^ww)/z>>2; } return w; } }; #endif