文章创作于 231130，250922 迁移至博客。

逻辑表达式

任意的命题公式都可以仅包含 $\{ \neg,\vee \}$ 或 $\{ \neg,\wedge \}$ 的命题公式等价代换。

与运算和或运算（掩码）

单片机中寄存器设置常用。

/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 */
int logicalNeg(int x) {
  int res=x;
  res |=  res>>16;
  res |=  res>>8;
  res |=  res>>4;
  res |=  res>>2;
  res |=  res>>1;
  res = ~res;
  res &= 0x01;
  return res;
}

在站内文章计算汉明重量的两个技巧性算法中，介绍了 Brian Kernighan 算法中的与运算技巧， x 和 x-1 进行与运算所得的结果为 x 删去其二进制表示中最右侧的 1 的结果。

异或

异或满足交换律和结合律。

\begin{align} a\oplus 0&=a \\ a\oplus a &= 0 \\ a\oplus b &= b\oplus a \\ (a \oplus b) \oplus c &= a \oplus( b \oplus c) \end{align}

两个数异或的结果意味着：

如果二进制结果中第 i 位为 1，说明这两个数在第 i 位上不相同
如果二进制结果中第 i 位为 1，说明这两个数在第 i 位上相同

我们可以使用异或实现一些函数：

/* 判断数字是否相等
* 要求只允许使用位运算符号
* 只返回0或1
*/
int is_equal(int x,int y){
	return !!(x^y);
}

/* 实现三元运算符
* x ? y : z
* 利用 x^x==0
*/
int conditional(int x, int y, int z) {
  int mix = y^z;
  int signal = !!x;
  signal = (signal<<31)>>31;
  return ((signal&z)|((~signal)&y))^mix; // y^z^y =z; z^y^z = y
}

补码

一个补码表示的二进制数 x，通过「取反加一」的方式得到其补码表示的 -x。

取反加一得到自身的特殊情况：

TMin 取反加 1 仍得到 TMin。符号位前后都是 1
0 取反加 1 得到 0。符号位前后都是 0。

至于其它数 x，取反加一得到的 -x 的符号位将会变化。

那么，加上异或的判断数字相等的特性，我们可以：

得出结论 x 不为 0 或 TMin 时，(~x+1)^x 结果的符号位为 1。
验证一个数是否为 TMin、TMax

取出一个整数的二进制表示中的最低位

快速计算补码的非有两种思考方式：

补码的非 -x==~x+1
找出数 x 中最右边的为 1 的位（只要 x 不是 0，总能找到），将这个 1 的左边所有的位取反。

根据第二种思考方式，我们可以得出：取出一个整数的二进制表示中的最低位 lowbit(x) 可以通过 x&-x 得到。

例子

数字 10 的二进制表示： 0b01010
数字 -10 的二进制表示：0b10110
5&-5 的结果： 0b00010

该技巧的应用文章：站内文章在线性时间内找出只出现 1 次的数字、站内文章树状数组上手了就十分简单。

计算一个数的补码表示至少需要多少比特

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5  
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4  
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  int sign = x>>31;
  int high16,high8,high4,high2,high1,high0;

  // sign ? -x : x;
  int mix = x^(~x);
  x = ((sign&(x))|((~sign)&(~x)))^mix;
  
  high16 = !!(x>>16);
  x >>= (high16<<4);

  high8 = !!(x>>8);
  x >>= (high8<<3);

  high4 = !!(x>>4);
  x >>= high4<<2;

  high2 = !!(x>>2);
  x >>= high2<<1;

  high1 = !!(x>>1);
  x >>= high1;

  high0 = x; //

  return (high16<<4) + (high8<<3) + (high4<<2) + (high2<<1) + high1 + high0 + 1 ; 
}