bits.cc

#include <iostream>
#include <vector>

int getNumSetBits(int num)
{
  int cnt = 0;
  while (num) {
    num &= num - 1;
    cnt++;
  }
  return cnt;
}

int getNumSetBitsFast(int num)
{
  int numBits[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 3, 3, 2, 3, 3, 4};
  int cnt = 0;
  while (num) {
    cnt += numBits[num & 0xF];
    num >>= 4;
  }
  return cnt;
}

bool isOddParity(int num)
{
  return (getNumSetBits(num) & 1) ? true : false;
}

bool isEvenParity(int num)
{
  return (getNumSetBits(num) & 1) ? false : true;
}

void setBit(int& num, int bit)
{
  num |= (1 << bit);
}

void clearBit(int& num, int bit)
{
  num &= ~(1 << bit);
}

bool isBitClear(int num, int bit)
{
  return (((num >> bit) & 1) == 0);
}

unsigned char rotate(unsigned char s, int n)
{
  return (s >> n) | (s << (8 - n));
}

bool isBitSet(int num, int bit)
{
  return (num & (1 << bit));
}

bool isPalindrome(int num)
{
  for (int i = 0, j = sizeof(num) - 1; i < j; i++, j--) {
    if (isBitSet(num, i) != isBitSet(num, j)) {
      return false;
    }
  }

  return true;
}

bool isBitSet(const char* data, int bit)
{
  return data[bit / 8] & (1 << bit % 8);
}

bool isPalindrome(const char* data, int numBits)
{
  if ((data == nullptr) || (numBits == 0)) {
    return false;
  }

  for (int i = 0, j = numBits - 1; i < j; i++, j--) {
    if (isBitSet(data, i) != isBitSet(data, j)) {
      return false;
    }
  }

  return true;
}

static int getNumTrailingZeros(int num)
{
  int cnt = 0;
  while ((num & 1) == 0) {
    cnt++;
    num >>= 1;
  }
  return cnt;
}

static int getNumTrailingOnes(int num)
{
  int cnt = 0;
  while ((num & 1) == 1) {
    cnt++;
    num >>= 1;
  }
  return cnt;
}

int getNextNumWithSameOnes(int num)
{
  if (num <= 0) {
    return -1;
  }

  int numTrailingZeros = getNumTrailingZeros(num);
  int numTrailingOnes = getNumTrailingOnes(num >> numTrailingZeros);

  int i = numTrailingZeros + numTrailingOnes;

  num |= 1 << i;
  i--;

  while (i >= (numTrailingOnes - 1)) {
    num &= ~(1 << i);
    i--;
  }

  while (i >= 0) {
    num |= (1 << i);
    i--;
  }

  return num;
}

int getPrevNumWithSameOnes(int num)
{
  if (num <= 0) {
    return -1;
  }

  int numTrailingOnes = getNumTrailingOnes(num);
  int numTrailingZeros = getNumTrailingZeros(num >> numTrailingOnes);

  int i = numTrailingZeros + numTrailingOnes;

  num &= ~(1 << i);
  i--;

  while (i >= (numTrailingZeros - 1)) {
    num |= (1 << i);
    i--;
  }

  while (i >= 0) {
    num &= ~(1 << i);
    i--;
  }

  return num;
}

int numBytesUtf8(char data)
{
  int cnt = 0;
  while (data & 0x80) {
    cnt++;
    data <<= 1;
  }
  return cnt == 0 ? 1 : cnt;
}

/*
 * A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
 * For 1-byte character, the first bit is a 0, followed by its unicode code.
 * For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1
 * bytes with most significant 2 bits being 10.
 */
bool isValidUtf8(const std::vector<char>& vec)
{
  if (vec.empty()) {
    return false;
  }

  int sz = vec.size();

  for (int i = 0; i < sz;) {
    if ((vec[i] >> 6) == 2) {
      return false;
    }
    int numBytes = numBytesUtf8(vec[i]);
    if (i + numBytes > sz || numBytes > 4) {
      return false;
    }
    for (int j = i + 1; j < i + numBytes; j++) {
      if ((vec[j] & 0x80) != 0x80) {
        return false;
      }
    }
    i += numBytes;
  }

  return true;
}

int main() {}