bitcrap.cpp

#include <stdint.h>
#include <stdio.h>

template<typename T> T get_bits(T value, unsigned msb, unsigned lsb) {
    return (value >> lsb) & ((1 << (msb - lsb + 1)) - 1);
}

template<typename T, unsigned N = (sizeof(T) * 8)> int log2(T value) {
    unsigned i = 0;
    while (i < N && (value >>= 1)) {
        i++;
    }

    return i;
}

// Specialization for signed types that cast to the right unsigned version.
template<> int log2<int64_t>(int64_t value) {
    return log2<uint64_t, sizeof(uint64_t) * 8>(value);
}

template<> int log2<int32_t>(int32_t value) {
    return log2<uint32_t, sizeof(uint32_t) * 8>(value);
}

template<> int log2<int16_t>(int16_t value) {
    return log2<uint16_t, sizeof(uint16_t) * 8>(value);
}

template<> int log2<int8_t>(int8_t value) {
    return log2<uint8_t, sizeof(uint8_t) * 8>(value);
}

// LowestSetBit(x) is the minimum bit number of any of its bits that are ones. If all of its bits are zeros, LowestSetBit(x) = N.
template<typename T, unsigned N = (sizeof(T) * 8)> int LowestSetBit(T value) {
    // If zero then return bit size of T.
    if (!value) {
        return N;
    }

    // Clear all values but the lowest set bit.
    T tmp = value & ~(value - 1);
    return log2<T, N>(tmp);
}

// HighestSetBit(x) is the maximum bit number of any of its bits that are ones. If all of its bits are zeros, HighestSetBit(x) = -1.
template<typename T, unsigned N = (sizeof(T) * 8)> int HighestSetBit(T value) {
    if (!value) {
        return -1;
    }

    return log2<T, N>(value);
}

// Number of zero bits at the left end of x, in the range 0 to N.
template<typename T, unsigned N = (sizeof(T) * 8)> int CountLeadingZeroBits(T value) {
    return N - 1 - HighestSetBit<T, N>(value);
}

// Number of copies of the sign bit of x at the left end of x, excluding the sign bit itself, and is in the range 0 to N-1.
template<typename T, unsigned N = (sizeof(T) * 8)> int CountLeadingSignBits(T value) {
    int count = 0;
    for (int i = (N - 2); i >= 0; i--) {
        if (!(value & (1ULL << i))) {
            break;
        }

        count++;
    }

    return count;
}

int main(int argc, char **argv) {
  printf("LowestSetBit\n");
  int64_t val0 = 0;
  unsigned t0 = LowestSetBit(val0);
  printf("0x%.16llx %u i=%u\n", val0, t0, 0);
  for(unsigned i = 0; i < sizeof(val0) * 8; i++ ){
    val0 = (1ULL << i);
    t0 = LowestSetBit(val0);
    printf("0x%.16llx %u i=%u\n", val0, t0, i);
  }  
  printf("\n");

  printf("HighestSetBit\n");
  val0 = 0;
  t0 = HighestSetBit(val0);
  printf("0x%.16llx %u i=%u\n", val0, t0, 0);
  for(unsigned i = 0; i < sizeof(val0) * 8; i++ ){
    val0 = (1ULL << i);
    t0 = HighestSetBit(val0);
    printf("0x%.16llx %u i=%u\n", val0, t0, i);
  }  
  printf("\n");  

  printf("CountLeadingZeroBits\n");
  val0 = 0;
  t0 = CountLeadingZeroBits(val0);
  printf("0x%.16llx %u i=%u\n", val0, t0, 0);
  for(unsigned i = 0; i < sizeof(val0) * 8; i++ ){
    val0 = (1ULL << i);
    t0 = CountLeadingZeroBits(val0);
    printf("0x%.16llx %u i=%u\n", val0, t0, i);
  }  
  printf("\n");  

  printf("CountLeadingSignBits\n");
  val0 = -1;
  t0 = CountLeadingSignBits(0);
  printf("0x%.16llx %u i=%u\n", 0, t0, 0);
  for(unsigned i = 0; i < sizeof(val0) * 8; i++ ){
    t0 = CountLeadingSignBits(val0);
    printf("0x%.16llx %u i=%u\n", val0, t0, i);
    val0 -= (1ULL << i);
  }  
  printf("\n");  
}