位运算操作详解与应用

"位运算操作" 位运算操作是计算机科学中的一种基本操作，它涉及到对整数的二进制表示进行直接处理。在处理位运算时，通常假设这些运算是在无符号整数（如unsigned或word类型）上进行的，因为它们只能表示正数。以下是一些常见的位运算及其应用： 1. **右移运算（shr）**：例如`xshr1`将一个数的二进制表示向右移动一位，相当于除以2，同时丢弃最右侧的位。例如，`101101 shr 1`得到`10110`。 2. **左移运算（shl）**：`xshl1`将一个数的二进制表示向左移动一位，相当于乘以2。例如，`101101 shl 1`得到`1011010`。 3. **异或运算（xor）**：用于改变特定位置的位。`xor1`可以将最后一位取反，如果最后一位是1，则变为0；如果最后一位是0，则变为1。例如，`101101 xor 1`得到`101100`，而`101101 xor (-1)`（即`11111111...1111`）将反转所有位。 4. **按位与（and）**和**按位非（not）**：`xandnot(1shl(k-1))`可以用来把右数第k位设为0，因为`1shl(k-1)`生成一个二进制数，其中只有第k位是1，其余位是0，然后通过按位与操作实现。类似地，`xxor(1shl(k-1))`可以用来翻转第k位。 5. **取模运算的位操作**：`xand7`取末三位，因为它相当于与二进制的`000111`（十进制的7）进行按位与操作。`xand(1shlk-1)`用于取末k位。 6. **位转换**：`xshr(k-1)and1`可以得到右数第k位的值，因为右移k-1位后，原来第k位的值会移动到最低位，然后与1进行按位与操作。 7. **位填充**：`xor(1shlk-1)`可以将末k位全部设为1，`xxor(1shlk-1)`则会反转末k位的值。 8. **清除右边连续的1**：`xand(x+1)`将右边连续的1变成0，因为`x+1`会产生一个与x相邻的位翻转的数，与x按位与后，相邻的1会被清除。 9. **设置右起第一个0位**：`xor(x+1)`会找到右起第一个0位并将其变为1，因为`x+1`会在x的第一个0位之后产生一个新的1。 10. **填充右边连续的0**：`xor(x-1)`将右边连续的0变成1，利用了与x-1异或时，x的每个1都会变为0，而每个0都会变为1的性质。 11. **取右边连续的1**：`xxor(x+1)`的结果右移1位后，可以得到`100101111->1111`，即x中从右向左的连续1序列。 12. **去掉右起第一个1的左边**：`xand(xxor(x-1))`可以实现这一操作，`xxor(x-1)`会将x中从右向左的连续1序列变为0，然后与x进行按位与，删除第一个1及其左侧的所有1。 在Pascal和C语言中，16进制数可以用特定的前缀表示，Pascal中用`$`，C中用`0x`。对于整数的存储，无符号整数和有符号整数在内存中表示方式不同，有符号整数通常采用补码表示法，而位运算通常只适用于无符号整数，因为它们不考虑符号位。理解这些概念对于深入理解计算机内部工作原理和优化算法至关重要。