EABitTricks

Introduction

EABitTricks provides a number of integer bit-manipulation utilities that are very fast and simple. For example, it is well-known that (x * 2) can be also accomplished with (x << 1). And while this example may not be useful in practice, there are many more such tricks which have real use, particularly for speeding up code. Some of these tricks may seem odd or even useless, but it turns out that there are surprising uses for many of these.

Notes

Example usage

All examples presume a #include "Foundation/EABitTricks.h" and assume the using of namespace EA.

TurnOffLowestBit

int16_t i16 = 0x0005;           // i16 => 000000101
i16 = TurnOffLowestBit(i16);    // i16 => 000000100
IsolateSingle0And1Bits
uint32_t u32 = 0xabababab;                // u32 => 10101011101010111010101110101011
u32 = IsolateSingle0And1Bits(0xabababab); // u32 => 11111100011111000111110001111100
RoundUpToPowerOf2
uint32_t u32 = 66;                // u32 => 66  (01000010)
u32 = RoundUpToPowerOf2(u32);     // u32 => 128 (10000000)

UnsignedMultiplyWouldOverflow

bool b = UnsignedMultiplyWouldOverflow(0xffffffff, 0xffffffff);  // b => true 

Interface

The following is a simple listing of EABitTricks functions as of January 2006. For an up to date listing of current functionality, see EABitTricks.h. Also, the EABitTricks.h file has documentation and example usage for each function.

Bit manipulation

T        TurnOffLowestBit(T x);
T        IsolateLowestBit(T x);
T        IsolateLowest0Bit(T x);
T        GetTrailing0Bits(T x);
T        GetTrailing1And0Bits(T x);
T        PropogateLowestBitDownward(T x);
T        TurnOffLowestContiguousBits(T x);
T        TurnOnLowest0Bit(T x);
uint32_t GetNextWithEqualBitCount(uint32_t x);
uint32_t IsolateSingleBits(uint32_t x);
uint32_t IsolateSingle0Bits(uint32_t x);
uint32_t IsolateSingle0And1Bits(uint32_t x);
int32_t  ShiftRightSigned(int32_t x, uint32_t n);
uint32_t CountTrailing0Bits(uint32_t x);
uint32_t CountLeading0Bits(uint32_t x);
uint32_t CountBits(uint32_t x);
uint32_t CountBits64(uint64_t x);
uint32_t RotateLeft(uint32_t x, uint32_t n);
uint32_t RotateRight(uint32_t x, uint32_t n);
uint32_t ReverseBits(uint32_t x);
uint32_t IsolateHighestBit(uint32_t x);
uint32_t IsolateHighest0Bit(uint32_t x);
uint32_t PropogateHighestBitDownward(uint32_t x);
uint32_t GetHighestContiguous0Bits(uint32_t x);
T        GetBitwiseEquivalence(T x, T y);
bool     AreLessThan2BitsSet(int32_t x);
T        GetHighestBit(T t);
  

Alignment / Power of 2

bool     IsPowerOf2(T x);
uint32_t RoundUpToPowerOf2(uint32_t x);
bool     IsMultipleOf(T x);
bool     IsPowerOf2Minus1(T x);
uint32_t GetHighestBitPowerOf2(uint32_t x);
bool     CrossesPowerOf2(T x, T y, T n);
bool     CrossesPowerOf2(T x, T y);
T        GetNextGreaterEven(T x);
T GetNextGreaterOdd(T x); T RoundUpTo(T x); int32_t RoundUpToEx(T x); T RoundDownTo(T x); T RoundDownToEx(T x); uint32_t Log2(uint32_t x);

Overflow

bool SignedAdditionWouldOverflow(T x, T y);
bool SignedSubtractionWouldOverflow(T x, T y);
bool UnsignedAdditionWouldOverflow(T x, T y);
bool UnsignedSubtractionWouldOverflow(T x, T y);
bool UnsignedMultiplyWouldOverflow(uint32_t x, uint32_t y);
bool SignedMultiplyWouldOverflow(int32_t x, int32_t y);
bool UnsignedDivisionWouldOverflow(uint32_t x, uint32_t y);
bool SignedDivisionWouldOverflow(int32_t x, int32_t y);
int  GetAverage(int32_t x, int32_t y);
int  GetAverage_Ceiling(int32_t x, int32_t y);

Miscellaneous

int32_t GetParity(uint32_t32_t x);
bool    GetIsBigEndian();
int32_t ToggleBetween0And1(int32_t x);
T       ToggleBetweenint32_tegers(T x, T a, T b);
bool    IsBetween0AndValue(int32_t x, int32_t a);
void    ExchangeValues(T& x, T& y);
T       FloorMod(T n, T mod);
int32_t GetSign(int32_t32_t x);
int32_t GetSignEx(int32_t32_t x);
int32_t SignExtend12(int32_t32_t x);
int32_t SignExtend24(int32_t32_t x);
bool    IsUnsigned(T x);
#define EAIsUnsigned(x)
bool    IsTwosComplement();
bool    IsOnesComplement();
bool    IsSignMagnitude();
bool    IsOffsetBinary();
#define EAArrayCount(array);