第一章：走进二进制的世界

1.1 计算机的语言：二进制

我们日常生活中使用十进制计数，逢十进一。但计算机内部，所有的数据——无论是数字、字符还是图片——都以二进制的形式存在。二进制是计算机能够直接理解的语言。

二进制，顾名思义，逢二进一。它只使用两个符号：$0$ 和 $1$。计算机中的一个晶体管可以表示两种状态，导通（高电平）或截止（低电平），正好对应 $1$ 和 $0$。无数个这样的晶体管组合起来，就能表示海量的信息。

• 位 (bit)：一个二进制位，是计算机中数据的最小单位，值为 $0$ 或 $1$。
• 字节 (Byte)：通常 $1$ 字节等于 $8$ 位。一个字节可以表示 $2^8 = 256$ 种不同的状态。

在C++中，一个 int 类型通常占用 $4$ 个字节，即 $32$ 位。这意味着一个 int 变量可以表示 $2^{32}$ 个不同的数值，对于有符号的 int，其表示范围通常是 $-2^{31}$ 到 $2^{31}-1$。

数制转换

• 二进制转十进制：按权展开求和。 例如，二进制数 $1101_2$ 转换为十进制：

  $$(1101)_2 = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 8 + 4 + 0 + 1 = 13 $$

• 十进制转二进制：短除法，倒取余数。 例如，将十进制数 $13$ 转换为二进制：

  13 / 2 = 6 ... 1
  6  / 2 = 3 ... 0
  3  / 2 = 1 ... 1
  1  / 2 = 0 ... 1
  

  从下往上读取余数，得到 $(1101)_2$。

• 十六进制：为了更紧凑地表示二进制数，引入了十六进制。它使用 $0-9$ 和 $A-F$ 来表示 $0-15$。一个十六进制位恰好可以表示 $4$ 个二进制位。

  • 例如：$(1101)_2 = (D)_{16}$，$(1010)_2 = (A)_{16}$。

1.2 什么是位运算

位运算（Bitwise Operation）是直接对整数在内存中的二进制位进行操作的运算。由于它在最底层操作数据，所以速度极快，在算法竞赛和系统编程中扮演着至关重要的角色。

C++ 提供了六种主要的位运算符：

运算符	名称	描述
&	按位与	两位都为 $1$ 时，结果为 $1$
`		按位或
^	按位异或	两位不同时，结果为 $1$
~	按位非	逐位取反，$0$ 变 $1$，$1$ 变 $0$
<<	左移	所有位向左移动，右侧补 $0$
>>	右移	所有位向右移动，左侧补位规则与符号有关

第二章：核心位运算符详解

为了方便演示，我们假设操作数是 $8$ 位的整数。

2.1 按位与 (AND - &)

规则：对两个数的二进制表示的每一位进行比较，如果两个相应的位都为 $1$，则结果的该位为 $1$，否则为 $0$。

• $1 \ \& \ 1 = 1$
• $1 \ \& \ 0 = 0$
• $0 \ \& \ 1 = 0$
• $0 \ \& \ 0 = 0$

示例：计算 $13 \ \& \ 10$

$13$ 的二进制是 $00001101$ $10$ 的二进制是 $00001010$

  00001101  (13)
& 00001010  (10)
------------------
  00001000  (8)

所以，$13 \ \& \ 10 = 8$。

常见用途

1. 判断奇偶：一个数是偶数，当且仅当其二进制的最低位是 $0$。因此，用这个数和 $1$ 进行按位与运算，如果结果是 $0$，则为偶数；如果结果是 $1$，则为奇数。

   $$x \ \& \ 1 == 0 \iff x \text{ is even}$$

2. 特定位清零：想将一个数 $x$ 的第 $k$ 位（从右数，第 $0$ 位开始）清零，只需让 $x$ 与一个只有第 $k$ 位是 $0$、其余位都是 $1$ 的数相与。这个数可以通过 ~(1 << k) 得到。

3. 获取二进制最低位的1：x & -x，这个技巧我们稍后在 lowbit 操作中详细介绍。

示例代码：判断奇偶

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int x;
    cin >> x;
    if ((x & 1) == 0) { // 使用按位与判断最低位
        cout << "Even\n";
    } else {
        cout << "Odd\n";
    }
    return 0;
}
// 时间复杂度: O(1)
// 空间复杂度: O(1)

2.2 按位或 (OR - |)

规则：对两个数的二进制表示的每一位进行比较，如果两个相应的位中至少有一个为 $1$，则结果的该位为 $1$，否则为 $0$。

• $1 \ | \ 1 = 1$
• $1 \ | \ 0 = 1$
• $0 \ | \ 1 = 1$
• $0 \ | \ 0 = 0$

示例：计算 $13 \ | \ 10$

$13$ 的二进制是 $00001101$ $10$ 的二进制是 $00001010$

  00001101  (13)
| 00001010  (10)
------------------
  00001111  (15)

所以，$13 \ | \ 10 = 15$。

常见用途

特定位置为1：想将一个数 $x$ 的第 $k$ 位置为 $1$，只需让 $x$ 与一个只有第 $k$ 位是 $1$、其余位都是 $0$ 的数相或。这个数就是 1 << k。

示例代码：将第 k 位置为 1

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k; // 输入整数n和位数k
    int res = n | (1 << k); // 将n的第k位置为1
    cout << res << '\n';
    return 0;
}
// 时间复杂度: O(1)
// 空间复杂度: O(1)

2.3 按位异或 (XOR - ^)

规则：对两个数的二进制表示的每一位进行比较，如果两个相应的位不同，则结果的该位为 $1$，否则为 $0$。可以理解为“无进位的加法”。

• $1 \ \hat{} \ 1 = 0$
• $1 \ \hat{} \ 0 = 1$
• $0 \ \hat{} \ 1 = 1$
• $0 \ \hat{} \ 0 = 0$

示例：计算 $13 \ \hat{} \ 10$

$13$ 的二进制是 $00001101$ $10$ 的二进制是 $00001010$

  00001101  (13)
^ 00001010  (10)
------------------
  00000111  (7)

所以，$13 \ \hat{} \ 10 = 7$。

重要性质

1. 归零律: $a \ \hat{} \ a = 0$ (任何数与自身异或，结果为0)
2. 恒等律: $a \ \hat{} \ 0 = a$ (任何数与0异或，结果是其本身)
3. 交换律: $a \ \hat{} \ b = b \ \hat{} \ a$
4. 结合律: $a \ \hat{} \ (b \ \hat{} \ c) = (a \ \hat{} \ b) \ \hat{} \ c$

常见用途

1. 不使用临时变量交换两个数：

   a = a ^ b;
   b = b ^ a; // b = (a^b)^b = a^(b^b) = a^0 = a
   a = a ^ b; // a = (a^b)^a = (a^a)^b = 0^b = b
   

2. 找出数组中唯一出现奇数次的元素： 将数组中所有元素进行异或，根据性质，出现偶数次的元素两两异或后都变成了 $0$，最后剩下的结果就是那个只出现奇数次的元素。

示例代码：找出唯一成单的数

题意概括：一个数组中，除了一个数字出现一次外，其他所有数字都出现了两次。找出这个只出现一次的数字。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n; // 数组元素个数 (实际上不需要n，可以直接读入)
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        res ^= x; // 将所有数异或起来
    }
    cout << res << '\n';
    return 0;
}
// 时间复杂度: O(N)，其中 N 是数组大小
// 空间复杂度: O(1)

2.4 按位非 (NOT - ~)

规则：这是一个单目运算符，对一个数的所有二进制位进行取反操作，$0$ 变为 $1$，$1$ 变为 $0$。

示例：计算 ~13 (在8位环境下)

$13$ 的二进制是 $00001101$ ~13 的结果是 $11110010$

在计算机中，整数通常使用**补码（Two's Complement）**表示。对于一个正数，其原码、反码、补码都相同。对于一个负数，其补码的计算方法是：符号位不变，其余各位取反，最后加 $1$。

一个重要的关系是：对于任意整数 $x$，都有 ~x = -x - 1。所以 ~13 在实际计算中（如 int 类型）会得到 -14。请注意，上面的二进制 11110010 只是一个8位环境下的演示。在典型的32位 int 中，~13 的结果将是 0xFFFFFFF2，但其对应的十进制数值依然是-14。

2.5 左移 (Left Shift - <<)

规则：x << k 将 $x$ 的二进制表示向左移动 $k$ 位，右边空出的位用 $0$ 填充。左边移出的位被丢弃。

示例：计算 $13 << 2$

$13$ 的二进制是 $00001101$ 左移 $2$ 位后变为 $00110100$

$00110100_2 = 32 + 16 + 4 = 52$。 可以发现，$13 \times 2^2 = 13 \times 4 = 52$。

核心效果：在不发生溢出的情况下，x << k 等价于 $x \times 2^k$。这是计算乘以2的幂次方的最快方法。需要特别注意的是，对于有符号整数，如果左移导致符号位被改变（例如一个正数左移后变成了负数），或者溢出了其可表示范围，其行为在C++标准中是未定义行为 (Undefined Behavior)。在竞赛中，为避免此类问题，进行位运算时常使用 unsigned 或 long long 等无符号或范围更大的类型。

2.6 右移 (Right Shift - >>)

规则：x >> k 将 $x$ 的二进制表示向右移动 $k$ 位，右边移出的位被丢弃。

左边空出的位如何填充，取决于操作数类型：

1. 逻辑右移：对于无符号数 (unsigned int)，左边总是用 $0$ 填充。
2. 算术右移：对于有符号数 (int)，左边用符号位填充。如果原数是正数（符号位为0），则补 $0$；如果原数是负数（符号位为1），则补 $1$。这样可以保持数的正负性。

核心效果：x >> k 的效果等价于将 $x$ 除以 $2^k$ 并向下取整（floor）。

• 对于非负数，这与C++中的 / 运算符结果一致。例如 13 >> 2 得到 3，13 / 4 也得到 3。
• 对于负数，结果则与 / 运算符不同。C++中的 / 运算符执行的是向零截断的除法（例如 -13 / 4 结果是 -3），而算术右移是向下取整（-13 >> 2 结果是 -4）。在处理负数时必须注意这一关键差异。

示例1 (正数)：计算 $13 >> 2$ $13$ 的二进制是 $00001101$ 右移 $2$ 位后变为 $00000011$ $00000011_2 = 3$。 这相当于 $13 / 2^2 = 13 / 4 = 3$ (向下取整)。

示例2 (负数)：计算 -13 >> 2 (假设8位补码) $13$ 是 $00001101$ -13 的补码是 $11110011$ 右移 $2$ 位（算术右移，补符号位1）后变为 $11111100$。 这个补码对应的十进制数是 $-4$。这符合 $(-13)/4$ 向下取整到 $-3.25 \to -4$ 的结果。

第三章：位运算组合技巧与实战

3.1 lowbit 操作：树状数组的基石

定义：lowbit(x) 函数返回 $x$ 在二进制表示下，最低位的 $1$ 以及它后面的 $0$ 所组成的数值。 例如，$x = 12$，其二进制是 $1100_2$。最低位的 $1$ 在第 $2$ 位（从右数，0-indexed），这个 $1$ 代表的数值是 $2^2 = 4$。所以 lowbit(12) = 4。

实现

$$\text{lowbit}(x) = x \ \& \ (-x)$$

原理： 计算机用补码存储负数。$-x$ 的补码等于对 $x$ 的二进制表示（除了符号位）取反加一，即 ~x + 1。

设 $x$ 的二进制为 ...10...0，其中最低位的 $1$ 右边有 $k$ 个 $0$。

• x 的形式是 ...A10...0 (A是更高位部分)
• ~x 的形式是 ...(~A)01...1 (k个1)
• -x (~x+1) 的形式是 ...(~A)10...0 (k个0)

将 $x$ 和 $-x$ 进行按位与操作：

  ...A10...0  (x)
& ...(~A)10...0  (-x)
--------------------
  ...010...0

高位部分 A 和 ~A 按位与后全部为 $0$。只有最低位的那个 $1$ 被保留下来。结果就是 $2^k$，即 lowbit(x) 的值。

用途：lowbit 是树状数组（Fenwick Tree）这一数据结构的核心操作，用于快速计算前缀和。

示例代码：实现 lowbit 函数

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int lowbit(int x) {
    return x & -x;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int x;
    cin >> x;
    cout << lowbit(x) << '\n'; // 演示lowbit函数
    return 0;
}
// 时间复杂度: O(1)
// 空间复杂度: O(1)

3.2 快速幂

题意概括：高效地计算 $a^b \pmod p$ 的值，其中 $a, b, p$ 都可能很大。

思路：直接循环 $b$ 次相乘的复杂度是 $O(b)$，当 $b$ 很大时会超时。 我们可以利用位运算进行优化。将指数 $b$ 进行二进制拆分。 例如，计算 $a^{13}$。 $13$ 的二进制是 $1101_2$，所以 $13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$。 因此，$a^{13} = a^{8+4+1} = a^8 \cdot a^4 \cdot a^1$。

我们可以通过循环，同时进行两件事：

1. 维护一个底数 a，在每次循环中自乘：$a \to a^2 \to a^4 \to a^8 \dots$
2. 检查 b 的二进制位，如果当前位是 $1$，就将当前维护的底数乘到最终结果 res 中。

b 的二进制位可以通过 b & 1 来判断最低位，然后通过 b >>= 1 来去掉最低位。

示例代码：快速幂

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll power(ll a, ll b, ll p) {
    ll res = 1;
    a %= p; // 预先取模
    while (b > 0) {
        if (b & 1) { // 如果b的当前最低位是1
            res = (res * a) % p; // 乘上当前的a
        }
        a = (a * a) % p; // a自乘，为下一位做准备
        b >>= 1; // b右移一位，处理下一位
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a, b, p;
    cin >> a >> b >> p;
    cout << power(a, b, p) << '\n';
    return 0;
}
// 时间复杂度: O(log b)，因为循环次数取决于b的二进制位数
// 空间复杂度: O(1)

3.3 状态压缩动态规划

核心思想：当动态规划的状态中，有一维表示一个集合（通常元素个数不多，例如 $N \le 20$），我们可以用一个整数的二进制位来表示这个集合。

• 整数的第 $i$ 位为 $1$，表示集合中包含第 $i$ 个元素。
• 整数的第 $i$ 位为 $0$，表示集合中不包含第 $i$ 个元素。

这样，对集合的操作（如添加元素、检查元素是否存在、合并集合）就可以用位运算高效完成。

• 检查元素 $i$ 是否在集合 S 中：if ((S >> i) & 1)
• 将元素 $i$ 加入集合 S：S | (1 << i)
• 从集合 S 中移除元素 $i$：S & (~(1 << i))
• 枚举集合 S 的所有子集 sub：for (int sub = S; sub; sub = (sub - 1) & S)

示例代码：旅行商问题 (TSP) 简化版

题意概括：给定 $N$ 个城市和它们之间的距离，从城市 $0$ 出发，经过每个城市恰好一次，最后回到城市 $0$，求最短的总路径长度。($N \le 20$)

思路： 定义 $dp[S][i]$ 表示：当前已经访问过的城市集合是 $S$，且最后停留在城市 $i$ 的最短路径长度。

• $S$ 是一个整数，它的二进制表示一个集合。
• 状态转移：要从状态 $dp[S][i]$ 转移出去，我们可以选择一个尚未访问过的城市 $j$ (即 !((S >> j) & 1) )，然后移动到 $j$。
  • 新的状态是 $dp[S \ | \ (1 << j)][j]$。
  • 转移方程：$dp[S \ | \ (1 << j)][j] = \min(dp[S \ | \ (1 << j)][j], dp[S][i] + \text{dist}(i, j))$

初始化：$dp = 0$ (只访问了城市0，停在城市0，路径长度为0)。 最终答案：$\min_{i=1}^{N-1} (dp[(1<<N)-1][i] + \text{dist}(i, 0))$，其中 $(1<<N)-1$ 是表示所有城市都被访问过的集合。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 20;
const int INF = 0x3f3f3f3f;
int w[N][N]; // 城市间距离
int dp[1 << N][N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> w[i][j];
        }
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0; // 初始化：只访问了0号点，当前在0号点

    for (int s = 1; s < (1 << n); ++s) { // 枚举所有状态集合
        for (int i = 0; i < n; ++i) { // 枚举当前停留的城市i
            if (!((s >> i) & 1)) continue; // i必须在集合s中

            for (int j = 0; j < n; ++j) { // 枚举下一个要去的城市j
                if ((s >> j) & 1) continue; // j不能在集合s中
                
                int nxt_s = s | (1 << j); // 新的状态
                dp[nxt_s][j] = min(dp[nxt_s][j], dp[s][i] + w[i][j]);
            }
        }
    }

    int full_s = (1 << n) - 1;
    int res = INF;
    for (int i = 1; i < n; ++i) { // 从各个终点回到起点0
        res = min(res, dp[full_s][i] + w[i][0]);
    }
    
    // 如果 n=1，特殊处理
    if (n == 1) res = 0;

    cout << res << '\n';

    return 0;
}
// 时间复杂度: O(N^2 * 2^N)
// 空间复杂度: O(N * 2^N)

第四章：例题

4.1 选择题与判断题

例1：表达式 (7 | 8) ^ 9 的值是？ A. 6 B. 15 C. 9 D. 0 解析：

1. 括号优先，计算 7 | 8。
   • $7 = (0111)_2$
   • $8 = (1000)_2$
   • $7 | 8 = (1111)_2 = 15$
2. 再计算 15 ^ 9。
   • $15 = (1111)_2$
   • $9 = (1001)_2$
   • $15 \ \hat{} \ 9 = (0110)_2 = 6$ 答案：A

例2：在32位系统中，执行 int x = -1; cout << (x >> 1); 后，输出结果是？ A. 2147483647 B. 0 C. -1 D. -2147483648 解析：

• int 是有符号类型，右移是算术右移。
• $-1$ 的补码表示是所有位都为 $1$ (即 0xFFFFFFFF)。
• 对一个全为 $1$ 的数进行算术右移，左边补入的也是 $1$。
• 所以右移后，结果仍然是所有位都为 $1$，其值依然是 $-1$。值得注意的是，这与C++中的除法不同：-1 / 2 的结果是 0（向零截断），而 -1 >> 1 的结果是 -1（向下取整）。 答案：C

4.2 程序阅读题

例：分析以下代码的功能。

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int x;
    cin >> x;
    int cnt = 0;
    while (x) { 
        x &= (x - 1);
        cnt++;
    }
    cout << cnt << '\n';
    return 0;
}

解析：

• 核心操作是 x &= (x - 1)，它等价于 x = x & (x - 1)。
• 这个操作的效果是，将 $x$ 在二进制表示下最低位的那个 $1$ 置为 $0$。
  • 例如 $x=12=(1100)_2$，$x-1=11=(1011)_2$。$12 \ \& \ 11 = 8 = (1000)_2$。成功消去了最低位的 $1$。
• while (x) 循环会一直执行，直到 x 的所有位都变为0，此时 x 的值就是 0，循环终止。
• cnt 变量记录了操作的次数。
• 因此，这段代码的功能是：计算整数 $x$ 的二进制补码表示中包含的 $1$ 的个数。
  • 这也是一个非常经典的位运算应用，通常被称为 popcount 或 bit_count。

4.3 程序补全题

这类题目会在一个算法框架中留空，需要你填入关键的位运算逻辑。

例：补全以下代码，使其能找到数组 a 中唯一一个出现奇数次的数字。

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, res = 0, x;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        // __________  补全代码
    }
    cout << res << '\n';
    return 0;
}

解析：

• 根据异或运算的性质（$a \ \hat{} \ a = 0$ 和 $a \ \hat{} \ 0 = a$），将所有数异或起来，成对出现的数会抵消为 $0$，最后剩下的就是那个单独的数。
• 所以，我们需要在循环中将每个读入的数 x 与 res 进行异或运算。
• 应填入：res ^= x;

位运算核心技巧与应用汇总表

分类	操作/技巧 (C++)	核心作用与二进制解释	常见用途与场景	备注与性质
基础运算	x & y	与: 对应位都为1时，结果位才为1。	判断奇偶: x & 1 特定位清零: x & ~(1 << k)	x & 0 = 0, x & x = x
	`x	y`	或: 对应位只要有1，结果位就为1。	特定位置1: `x
	x ^ y	异或: 对应位不同时为1，相同时为0。	翻转特定位: x ^ (1 << k) 交换两数(无临时变量) 找出唯一成单的数。	归零律: x ^ x = 0 恒等律: x ^ 0 = x 满足交换律、结合律
	~x	非: 翻转所有二进制位 (0变1，1变0)。	生成全1掩码: ~0	在补码表示中，~x = -x - 1
	x << k	左移: 所有位向左移动k位，右侧补0。	快速计算 $x \times 2^k$ 生成掩码 1 << k	对有符号数，若改变符号位或溢出，是未定义行为。
	x >> k	右移: 所有位向右移动k位，左侧补位。	快速计算 $\lfloor x / 2^k \rfloor$ (向下取整)。	对有符号数是算术右移(补符号位)，对无符号数是逻辑右移(补0)。
复合技巧	x & (x - 1)	将 x 最低位的那个 1 置为 0。	统计二进制中1的个数(popcount) 判断是否是2的幂: x > 0 && (x & (x-1)) == 0	每次操作消除最低位的1，非常高效。
	x & -x	得到 x 最低位的 1 所代表的数值 (lowbit)。	树状数组(Fenwick Tree)的核心。	原理基于补码 -x = ~x + 1
状态压缩	(S >> i) & 1	检查整数 S 的第 i 位是否为1。	状态压缩DP中，判断集合 S 是否包含元素 i。	将集合问题转化为整数位运算问题。
	`S	(1 << i)`	将整数 S 的第 i 位置为1。	状态压缩DP中，向集合 S 中添加元素 i。
	S & ~(1 << i)	将整数 S 的第 i 位清零。	状态压缩DP中，从集合 S 中移除元素 i。	幂等操作，对已为0的位无影响。
	S ^ (1 << i)	翻转整数 S 的第 i 位。	状态压缩DP中，切换元素 i 的存在状态。
	for(sub=S; sub; sub=(sub-1)&S)	枚举集合 S 的所有非空子集 sub。	状态压缩DP中，需要从一个状态转移到它的所有子集状态时。	总复杂度为 $O(3^N)$，指对所有 $2^N$ 个集合枚举其子集的总和。单个集合 S (大小为k) 的子集枚举为 $O(2^k)$。
内置函数	__builtin_popcount(x)	(GCC/Clang) 统计 x 中1的个数。	同 x & (x-1) 法，但通常更快。	对应 long long 的是 __builtin_popcountll(x)。
	__builtin_clz(x)	(GCC/Clang) 计算前导零(leading zeros)的个数。	可用于快速计算 $\lfloor \log_2 x \rfloor$	clz = count leading zeros. 参数为0时行为未定义。
	__builtin_ctz(x)	(GCC/Clang) 计算末尾零(trailing zeros)的个数。	lowbit(x) 的另一种求法是 1 << __builtin_ctz(x)	ctz = count trailing zeros. 参数为0时行为未定义。