位运算的应用 - 综合

创建时间:
2018-07-17 23:48
最近更新:
2018-08-12 23:40

Resource

  1. 二进制位的翻转 和 二进制表示中1的个数

给指定位赋值

如果需要将某位 置0 则 与 1111 1101;
如果需要将某位 置1 则 或 0000 0010。
已实现在 Tl.BitAndByte.BitSet()

整数的二进制的 奇数位 和 偶数位 交换位置

Write a program to swap odd and even bits in an integer with as few instructions as possible (用尽可能少的指令编写一个程序来交换整数中的奇数位和偶数位).

public static int swapOddEvenBits(int x)
{
    int swap =
        (x & 0xaaaaaaaa) >> 1
        |
        (x & 0x55555555) << 1
        ;
    return swap;
}

public static long swapOddEvenBits(long x)
{
    long swap =
        (x & 0xaaaaaaaaaaaaaaaa) >> 1
        |
        (x & 0x5555555555555555) << 1
        ;
    return swap;
}

Windows 10 的 计算器 "程序员" 模式 的 转换结果 备忘

hex: 5555
dec: 21845
bin: 101010101010101

hex: 55555555
dec: 1431655765
bin: 1010101010101010101010101010101

hex: 5555555555555555
dec: 6148914691236517205
bin: 101010101010101010101010101010101010101010101010101010101010101

hex: AAAA
dec: 43690
bin: 1010101010101010

hex: aaaaaaaa
dec: 2863311530
bin: 10101010101010101010101010101010

hex: aaaaaaaaaaaaaaaa
dec: -6148914691236517206
bin: 1010101010101010101010101010101010101010101010101010101010101010

Resource

  1. 将一个整数的二进制表示的奇数位与偶数位交换位置

反转二进制数

两个常用实现 详见 "Tl.BitAndByte.ReverseBits()"。

反转二进制数 (最巧妙的算法)

Source: 二进制位的翻转 和 二进制表示中1的个数

//求 char型数据 的 二进制表示 反转后对应的十进制数:
unsigned char reverse(unsigned char c)
{
    c = (c & 0x55) << 1 | (c & 0xAA) >> 1;
    c = (c & 0x33) << 2 | (c & 0xCC) >> 2;
    c = (c & 0x0F) << 4 | (c & 0xF0) >> 4;
    return c;
}
//求 十进制整数 的 二进制表示 反转后对应的十进制数:
unsigned int Bit_Reverse(unsigned int v)
{
    v = ((v >>  1) & 0x55555555) | ((v <<  1) & 0xaaaaaaaa);
    v = ((v >>  2) & 0x33333333) | ((v <<  2) & 0xcccccccc);
    v = ((v >>  4) & 0x0f0f0f0f) | ((v <<  4) & 0xf0f0f0f0);
    v = ((v >>  8) & 0x00ff00ff) | ((v <<  8) & 0xff00ff00);
    v = ((v >> 16) & 0x0000ffff) | ((v << 16) & 0xffff0000);
    return v;
}

算法是这样的: 首先是2位2位为一组,交换前一半和后一半。再4位4位为一组,交换前一半和后一半。再8位为一组,交换前一半和后一半。

例如将 1 2 3 4 5 6 7 8 反转:

  1. 2个2个为一组,交换前一半和后一半,变成: 2 1 4 3 6 5 8 7
  2. 4个4个为一组,交换前一半和后一半,变成: 4 3 2 1 8 7 6 5
  3. 8个8个为一组,交换前一半和后一半,变成: 8 7 6 5 4 3 2 1

至此反转成功。

这样的算法本来很是简单,很容易用数学归纳法证明其正确。这函数,巧妙就巧妙在作了并行计算,分组,它一次就计算完了。

先看第一个语句:
c = (c & 0x55) << 1 | (c & 0xAA) >> 1;
0x55 其实就是 01010101
0xAA 其实就是 10101010

假设 c = abcdefgh
c & 0x55 = 0b0d0f0h
c & 0xAA = a0c0e0g0

跟着,
前者左移一位变成 b0d0f0h0
后者右移一位变成 0a0c0e0g
再一个 | 运算,就两位两位交换了位置,变成 badcfehg

想象一下,你有一个长纸条,分成一格一格,每格写一个字,假如你将纸条每隔一格剪一个小洞,滑一格,覆盖在原来的纸条上,你就会看到两个两个字交换了位置。(注: | 运算可以换成 + 运算,想一想为什么)

第二个语句:
c = (c & 0x33) << 2 | (c & 0xCC) >> 2;
0x33 其实就是 00110011
0xCC 其实就是 11001100

第三个语句:
c = (c & 0x0F) << 4 | (c & 0xF0) >> 4;
0x0f 其实就是 00001111
0xF0 其实就是 11110000

第二、第三 两个语句的作用也是 分组,将一半位变成0,移位滑动,跟着再组合,就分组交换了位置。不妨想象两个小纸条剪洞叠加。

常用二进制位操作

功能 示例 位运算
去掉最后一位 101101 → 10110 x shr 1
在最后加一个 0 101101 → 1011010 x shl 1
在最后加一个 1 101101 → 1011011 x shl 1 + 1
把最后一位变成 1 101100 → 101101 x or 1
把最后一位变成 0 101101 → 101100 x or 1 - 1
最后一位取反 101101 → 101100 x xor 1
把右数第 k 位变成 1 101001 → 101101, k = 3 x or (1 shl (k - 1))
把右数第 k 位变成 0 101101 → 101001, k = 3 x and not (1 shl (k - 1))
右数第 k 位取反 101001 → 101101, k = 3 x xor (1 shl (k - 1))
取末三位 1101101 → 101 x and 7
取末 k 位 1101101 → 1101, k = 5 x and (1 shl k - 1)
取右数第 k 位 1101101 → 1, k = 4 x shr (k - 1) and 1
把末 k 位变成 1 101001 → 101111, k = 4 x or (1 shl k - 1)
末 k 位取反 101001 → 100110, k = 4 x xor (1 shl k - 1)
把右边连续的 1 变成 0 100101111 → 100100000 x and (x + 1)
把右起第一个 0 变成 1 100101111 → 100111111 x or (x + 1)
把右边连续的 0 变成 1 11011000 → 11011111 x or (x - 1)
取右边连续的 1 100101111 → 1111 (x xor (x + 1) ) shr 1
注1 去掉右起第一个 1 的左边 100101000 → 1000 x and (x xor (x - 1))

注1 常用于树状数组中。