11 9
C语言的位操作常见例子

我们每一种计算机语言最终都会通过编译器转换成机器语言来执行,所以在编程中,位操作是常见且高效的数据处理手段之一,下面列出一些基于C语言的场景实例,便于日常开发中学习和使用

例一,编写函数 getbits(x,p,n) 从数值x的第p位开始返回n位数值

#include <stdio.h>

int getbits(unsigned x, int p, int n);

int main() {
  unsigned x = 0xF994;
  int p = 4;
  int n = 3;
  int z = getbits(x, p, n);

  printf("getbits(%u (%x), %d, %d) = %u (%X)\n", x, x, p, n, z, z);
}

// ff94             11111111100.101.00  # original number
// >> p+1-n     [2] 0011111111100.101.  # shift desired bits to right
// & ~(~0 << n) [7] 0000000000000.101.  # clear all the other (left) bits

int getbits(unsigned x, int p, int n) { return x >> (p - n + 1) & ~(~0 << n); }

例二,编写一个函数setbits(x,p,n,y),该函数返回对x执行下列的操作的结果的值:将x中从左第p位开始的n个(二进制)位设置为y中最右边n位的值,x的其余各位保持不变

#include <stdio.h>

unsigned setbits(unsigned x, unsigned p, unsigned n, unsigned y);

int intLen(unsigned x);

int main() {

  unsigned x = 171; // 1010 1011 --- > 101[0 1]011
  unsigned p = 3;
  unsigned n = 2;
  unsigned y = 38; // 0010 0110

  printf("result : %u \n", setbits(x, p, n, y));

  return 1;
}

int intLen(unsigned x) {
  int len = 0;
  for (; x; x >>= 1) {
    len++;
  }
  return len;
}

unsigned setbits(unsigned x, unsigned p, unsigned n, unsigned y) {

  int length_y = intLen(y);
  int length_x = intLen(x);

  if (length_x - p - n < 0) {
    printf("move over size by x");
    return 0;
  }

  if (length_y < n) {
    printf("move over size by y");
    return 0;
  }

  // int pos = p -n + 1;
  // unsigned cpy = y & ~ (~0 << n);
  // unsigned xx = (x >> pos) & (~0 << n);
  // return xx |= cpy;

  unsigned tail = length_x - (p + n);

  // x需要分离的子数据
  unsigned sub = x & ~(~0 << tail);

  // y 中需要替换的n位数据
  unsigned cpy = y & ~(~0 << n);

  // x向右移位,保留左边
  x >>= length_x - p;

  // x再向左移,这样最右边的n为可以为0
  x <<= n;

  //这样可以把y的拷贝值拷贝过去
  x |= cpy;

  // x再向左推进, 把刚刚的分离的n为先补0先
  x <<= tail;

  // x的分离再补充回数值
  x |= sub;

  return x;
}

例三,编写一个函数invert(x,p,n), 该函数返回对x执行下列操作后的结果的值:将x中左起第p位开始的n个(二进制)位求反(即,1变成0,0变成1),x的其余各位保持不变

#include <stdio.h>

unsigned invert(unsigned x, unsigned p, unsigned n);

int intLen(unsigned x);

int main() {
  unsigned x = 171; // 1010 1011 --- > 101[0 1]011
  printf("result: %u\n", invert(x, 3, 2));
  return 1;
}

int intLen(unsigned x) {
  int len = 0;
  for (; x; x >>= 1) {
    len++;
  }
  return len;
}

unsigned invert(unsigned x, unsigned p, unsigned n) {

  int length_x = intLen(x);

  if (length_x - p - n < 0) {
    printf("move over size by x");
    return 0;
  }

  unsigned tail = length_x - (p + n);

  // x需要分离的子数据
  unsigned sub = x & ~(~0 << tail);

  // 0001 01[0 1]
  x >>= tail;

  // x ^= 0011
  // 0001 0110
  x ^= ~(~0 << n);

  // 101[10]000
  x <<= tail;

  // 101[10]011
  x |= sub;

  return x;
}

例四,编写一个函数rightrot(x,n):该函数返回将x循环右移(即从最右端移出的为将从最左端移入)n (二进制) 位后所得到的值

#include <stdio.h>

int intLen(unsigned x);

unsigned rightrot(unsigned x, int n);

int main() {
  unsigned x = 171; // 1010 1011
  int n = 5;

  // assert x = 01011 101 = 93
  printf("result = %u\n", rightrot(x, n));
  return 1;
}

int intLen(unsigned x) {
  int len = 0;
  for (; x; x >>= 1) {
    len++;
  }
  return len;
}

unsigned rightrot(unsigned x, int n) {
  int length_x = intLen(x);
  if (length_x) {
    n %= length_x;
    if (n) {
      // x需要分离的子数据
      unsigned sub = x & ~(~0 << n);

      // x 向右移动n位
      x >>= n;

      //计算左边位置需要填报多少位
      int mov = length_x - n;

      //通过上面分离的子串构造新的等长新串
      unsigned subx = sub << mov;

      subx ^= x;

      return subx;

    } else {
      return x;
    }
  }
  return 0;
}

例五,在求对二的补码时,表达式 x&(x-1) 可以删除x中最右边值为1的一个二进制位。用这一方法重写bitcount函数,以加快其执行速度

#include <stdio.h>

int bitcount(unsigned x);

int main() {
  printf("%d's bit count: %d\n", 1023, bitcount(1023));
  printf("%d's bit count: %d\n", 1024, bitcount(1024));
}

int bitcount(unsigned x) {
  int len = 0;
  for (; x; x &= x - 1) {
    len++;
  }
  return len;
}