C++ 宏定义与位操作

Macro & Bit Operations: 思考题与知识点。

提醒：不过多赘述「宏」以及本文相关的其它 C++ 基础知识，不明之处暂请自行 Google。

宏定义

即 Macro。

Print

Print Expr & Result
便捷地打印程序输出：变量或表达式，以及计算结果。

重复 cout << variable << endl; 这种用于打印程序输出的代码实在麻烦，但不得不写，

所以，为了更便捷地打印程序输出，写了一些辅助的「宏」。

#define v(x) cout << '\t' << #x << "  =  " << (x) << endl;

关键：用宏定义的展开，减少代码量。
#x 的语法可以获取 x 所代表的变量或表达式的具体内容。
(x) 中的括号不能去掉！否则可能会得出意想不到的错误结果。
提示：在程序的预处理阶段，会展开代码中「宏定义」，即对「宏名」进行简单的字符串替换，详情自行 Google。

打印工具的宏定义

// print_tools.h

// 说明："CPP_TEST" 为本 Demo 项目名
#ifndef CPP_TEST_PRINT_TOOLS_H
#define CPP_TEST_PRINT_TOOLS_H

using std::cout;
using std::endl;

// 打印字符串
#define l(str) cout << str << endl;

// 打印变量或表达式，及其结果
#define v(x) cout << '\t' << #x << "  =  " << (x) << endl;

// 打印一个空行（分隔不同的程序输出）
#define el cout << endl;

#endif //CPP_TEST_PRINT_TOOLS_H

这种声明是为了避免项目重复引入该头文件（即 #include "print_tools.h" ）时，重复定义其中的内容

// 作用：防止重复定义
#ifndef CPP_TEST_PRINT_TOOLS_H
#define CPP_TEST_PRINT_TOOLS_H
// …
#endif //CPP_TEST_PRINT_TOOLS_H

演示打印工具

// main.cpp

#include <iostream>
#include "print_tools.h" // 引入上述的宏
//using namespace std; // 不将整个 std 引入，因为其中很多东西都用不上。

/* 后文的样例中，需要额外引入的「库和对象」放这 */
#include <map>
using std::map;
// …

/* 宏定义 */
#define MAX(a, b) ((abs((a) - (b)) == (a) - (b)) ? (a) : (b))
// …

/* 「函数前置声明」放这 */
bool isIncr(int *ary, int count);
// …

int main() {
    /* 运行的「测试代码」放这 */
    l("test")
    int x = 1;
    int y = -1;
    v(x)
    v(x >> 31)
    v(y)
    v(y >> 31)
    el

    l("MAX")
    v(MAX(10, 20))
    v(MAX(-10, -20))
    el

    l("用一个递归算法，判断一个数组中的值，是否递增？")
    int ary = new int[5]{1, 4, 5, 9, 7};
    v(isIncr(ary, 5))
    delete []ary;
    ary = new int[5]{1, 4, 5, 7, 9};
    v(isIncr(ary, 5))
    delete []ary;
    el

    //…

    return 0;
}

/* 「函数定义」放这 */
bool isIncr(int *ary, int count); {
    return count == 1
        || (count != 0
            && ary[count - 2] <= ary[count - 1]
            && isIncr(ary, --count));
}
// …

# 输出

test
    x  =  1
    x >> 31  =  0
    y  =  -1
    y >> 31  =  -1

MAX
    MAX(10, 20)  =  20
    MAX(-10, -20)  =  -10

用一个递归算法，判断一个数组中的值，是否递增？
    isIncr(ary, 5)  =  0
    isIncr(ary, 5)  =  1

…

进阶可参考《宏定义的黑魔法 - 宏菜鸟起飞手册》

数值的大小关系

判断两个数值的大小关系。

// 以宏定义的方式实现
#define MAX(a, b) (abs((a) - (b)) == ((a) - (b)) ? (a) : (b))

数值的 sign

判断 signed（有符号）类型的数值的 sign（正负符号）。

// 以宏定义的方式实现
#define IS_UNSIGNED(a) (a >= 0 && ~a >= 0)

unsigned 数值类型

判断数值类型是否有符号（signed），即是否区分正负。

// 以宏定义的方式实现
#define IS_UNSIGNED_TYPE(type) ((type)0 - 1 > 0)

各种语言的数值类型基本都实现了正负值的区分（signed）

所以只使用 unsigned 来标识少数无符号的数值类型，而很少出现 signed 这种说法。

int 变量的 bytes

当前运行环境下（与 CPU 和 OS 有关），一个 int（整型）数值类型变量所占用的 bytes（字节数）。

// 以宏定义的方式实现
`#define SIZE_OF(value) ((char*)(&value + 1) - (char*)&value)`

宏定义语法 `##`

## 用于连接前后两段代码。

// 宏定义
#define CONCAT_CODE(a, b) (a##e##b)

// 测试代码
v(CONCAT_CODE(2, 3))

# 输出
CONCAT_CODE(2, 3)  =  2000

解释：

因为 CONCAT_CODE(2, 3) 将代码 2、e、3 连接成 2e3
等于 int 2 * pow(10, 3) = 2 * 1000 = 2000

位操作

即 Bit Operations，对数值（用二进制表示）的 bit（比特位）进行直接操作

int 整型数值

**整型，表示整数的数值类型

下文中，进行位操作的变量的类型，主要为 int 等表示整数的数值类型。

暂不包括浮点数，float、double、long。

int 可描述的数值范围：

32 位（bits）操作系统（OS）下，占用 4 bytes
- -2^32 ~ 2^32 - 1（此处 2^32 表示 2 的 32 次方）
64 位操作系统下，占用 8 bytes
- -2^64 ~ 2^64 - 1
下文中，默认运行环境为 32 位的操作系统。

数值表示方式

0x4F 中的 0x 表示该数值在以 16 进制进行展示；
'0010'B 中的 B 表示该数值在以 2 进制进行展示。
注意：C / C++ 中，不支持直接以 2 进制的形式声明数值；
- 如有需要，通常以 16 进制的形式声明和表示二进制数值（bits）。

以 16 进制展示数值：

0x 00 00 00 00 = int 0
0x 00 00 00 01 = int +1
0x FF FF FF FF = int -1

下文默认你知晓「在底层如何以二进制比特位来储存和表示整型数值，特别是『负数』。」

负数：以二进制方式进行储存和表示时，最高位（最左）的 bit 是 1。
int 0 在物理层面使用了 0x 00 00 00 00 这个数值来表示，
所以，int 等整数数值类型，所能描述的正数的范围被比负数范围小 1。

移位求积

快速求 int 2 的 3 次方

每左移一位，数值增大 2 倍（除非溢出）

2 << 3

快速求 int x 的 7 倍

(x << 3) - x

2 的幂

判断 int 数值是否为 2 的若干次幂（即 2 的 n 次方）

分析

数值在计算机中通常都以 0 和 1 的二进制形式存储着
其实关键在于，这个问题等价于判断一个整数的二进制形式是否「有且只有一位 bit 为 1」

// 测试代码
int x = 1024;
v(x)
v(std::bitset<12>(x))
v(!(x & (x - 1)))
x = 513;
v(x)
v(std::bitset<12>(x))
v(!(x & (x - 1)))

思路

x - 1 等价于「二进制表示的整数 x，从最后（右）一位 1 开始（包括这个 1）的所有 bit 都取反」
那么 x & (x - 1) 就是去除 x 二进制表示中的最后一个为 1 的 bit
如果去除最后一位 1 后 x 变成了 0 了，它就是 2 的若干次幂

# 输出
判断一个 int 是否为 2 的若干次幂
    x  =  1024
    std::bitset<12>(x)  =  010000000000
    !(x & (x - 1))  =  1
    x  =  513
    std::bitset<12>(x)  =  001000000001
    !(x & (x - 1))  =  0

求负数

以位操作的方式，求 int x 的负数

// `~` 是「按位取反」的操作符
-x = ~x + 1
-x = ~(x - 1)

不详述推导过程，只提供简单的记忆方式

假设现在的运行环境是 8 位的操作系统
- '00 00 00 00'B = int 0
- '00 00 00 01'B = int +1
- '11 11 11 11'B = int -1
对以上三个数值进行通过简单的观察和推算，就能得出上面提供的公式

求平均值

求两个 int 数值的平均值

一般求法

缺点：如果 x + y 的数值超出 int 可描述的数值范围（即溢出），会得出错误的结果。

(x + y) / 2

位操作的求法

(x & y) + ((x ^ y) >> 1)

提示：从二进制角度来说

(x & y) 等于「所有为 1 的 bit（比特位）相加的结果除以二」；
(x ^ y) >> 1 等于「将 x、y 两数相加等于 1 的 bit（一个为 0 另一个为 1）除以二」。

求绝对值

以位操作的方式，求 int x 的绝对值。

「求负数」的延伸。以下为思路：

sign（符号位）的计算

x < 0 时，x >> 31 = -1
x >= 0 时，x >> 31 = 0
>> 右移操作，最高位（最左）用原最高位的数值进行补位：
- 原最高位为 1，右移后，新的最高位补 1，
- 原最高位为 0，右移后，新的最高位补 0。

数值取反

~x = -1 ^ x = 0xFFFFFFFF ^ x
代入求负数的公式: -x = ~x + 1 = (-1 ^ x) + 1
注意：^ >> 等位操作符的优先级低于 + -，
- 所以，书写时不能漏掉括号，以免算式出错。

补充条件

x = 0 ^ x（进一步观察得到的，可能需要灵感）

观察规律

x < 0 时，abs(x) = -x = (-1 ^ x) + 1 = (-1 ^ x) - (-1)
x >= 0 时，abs(x) = x = 0 ^ x = (0 ^ x) - (0)

启示

abs(x) = ((x >> 31) ^ x) - (x >> 31)

解法

// 函数声明
int myAbs(int x) {
    int mask = x >> 31;
    return (mask ^ x) - mask;
}

// 测试代码
v(myAbs(0))
v(myAbs(1))
v(myAbs(-1))
v(myAbs(17))
v(myAbs(-29))

# 输出
myAbs(0)  =  0
myAbs(1)  =  1
myAbs(-1)  =  1
myAbs(17)  =  17
myAbs(-29)  =  29

多少个 bit 为 1

数值变量的二进制表示中，有多少个 bit（比特位）为 1。

说明：暂时想到的方法，还是需要用到循环（复杂度 o(n)）。
提示：为 1 的 bit 分布稀疏时，如何快速求解（减少代码所需循环次数）！
基础知识：将一个 int 变量（二进制表示中，从左到右数）最后一个为 1 的 bit 设置为 0：

b & (b - 1)

解法

// 函数声明
int countBit(int x) {
    int cnt = 0;
    while (x != 0) {
        ++cnt;
        x &= x - 1;
    }
    return cnt;
}

// 测试代码
v(countBit(46)) // int 46 == '0101110'B
v(countBit(21)) // int 37 == '0010101'B

# 输出
countBit(46)  =  4
countBit(21)  =  3

相邻 bit 不同时为 1

n 位的二进制数字串，有多少个子串不存在相邻的 bit 同时为 1。

思路

n == 1 时，有 0 和 1 两种符合条件的可能情况；
n == 2 时，则有 00、01 和 10 三种可能；
n == 3 时，则有 000、001、010、100、101 五种可能…

根据归纳法，我们发现它类似于斐波那契数列

// 函数声明
int separate1(unsigned int n) {
//    switch(n) {
//        case 1:
//            return 2;
//        case 2:
//            return 3;
//        default:
//            return separate1(n - 2) + separate1(n - 1);
//    }

    // 压缩
    return 1 == n ? 2 :
           2 == n ? 3 :
           separate1(n - 2) + separate1(n - 1);
}

// 测试代码
l("n 位的二进制数字串，有多少个子串不存在相邻的 bit 同时为 1")
v(separate1(1))
v(separate1(2))
v(separate1(3))
v(separate1(4))

# 输出
div1(1112, 12)  =  92
div2(1112, 12)  =  92

不用 `+` 的加法

不用加号完成加法

思路

在二进制下，对两个数的相加为 1 的 bit，用「^ 异或」来求和
对两个数相加为 0 并进位 1 的 bit，先进行「& 按位与」操作，然后「<< 1 进位」，然后再求和

// 函数声明：方法 1 - 递归
int add1(int x, int y) {
//    if (0 == y) {
//        return x;
//    }
//
//    int tmpSum = x ^ y;       // 求和
//    int carry = (x & y) << 1; // 进位
//    return add(tmpSum, carry);

    // 缩写
    return 0 == y ? x : add1(x ^ y, (x & y) << 1);
}

// 函数声明：方法 2 - 迭代
int add2(int x, int y) {
    int sum = 0;
    while (y != 0) {
        sum = x ^ y;
        y = (x & y) << 1;
        x = sum;
    }
    return sum;
}

// 测试代码
l("不用加号实现加法")
v(add1(98, 103))
v(add1(10, 6))
v(add2(98, 103))
v(add2(10, 6))

# 输出
不用加号实现加法
    add1(98, 103)  =  201
    add1(10, 6)  =  16
    add2(98, 103)  =  201
    add2(10, 6)  =  16

不用 `*` 的乘法

不用乘号完成乘法

思路

跟上文说的「不用 / 做除法」的思路类似，也是参考小学的时候学的「写草稿计算乘积」的算法。

基础：顺着上文「2 的幂」小节的思路，可以知道

得出一个 int 整数 最后一个为 1 的 bit 所代表的数值：

// 两个公式等价
b & ~(b - 1)
b & (-b)

// 函数声明
// 需要额外引用的工具库
#include <map>
using std::map;
using std::string;

int multiply(int x, int y) {
    bool neg = (y < 0);
    if (neg) {
        y = -y;
    }

    map<int, int> bitMap;
    for (int i = 0; i < 32; ++i) {
        bitMap[1 << i] = i;
    }

    int product = 0;
    while (y > 0) {
        // `被乘数 * 乘数` 找出乘数在二进制下的最后一位 1 在第 n 位
        int shiftBits = bitMap[y & ~(y - 1)];
        // 叠加被乘数自身被左移 n 位的值（即乘以 2 的次方）
        product += (x << shiftBits);
        // 去掉乘数在二进制下的最后一位为 1 的 bit！
        y &= (y - 1);
    }

    if (neg) {
        product = -product;
    }
    return product;
}

// 测试代码
l("不用乘号实现乘法")
v(multiply(10, 6))
v(multiply(29, 7))

# 输出
不用乘号实现乘法
    multiply(10, 6)  =  60
    multiply(29, 7)  =  203

大小端

判断内存以什么字节序储存数据：Big Endian or Little Endian 大小端？

简要说明大小端的区别（字节序）

内存 0x4000 ~ 0x4003 的低地址在左，高地址在右
- 内存地址 : 从低到高 / 从左到右增长
- 即 0x4000 0x4001 0x4002 0x4003
- 数据从低地址开始存放 (从左往右存放)
数据 0x 12 34 56 78 高位 (高字节) 在左，低位 (低字节) 在右！
- 字节高低 : 从高到低 / 从左到右排列
- 即 12 在高位/高字节, 78 在低位/低字节
小端：从右到左 存放数据 (网络传输常用顺序)
- 低位/低字节从 低地址 开始放 : 78 56 34 12
- 即鸡蛋从小的一头开始敲开蛋壳 Big-Endian
大端：从左到右 存放数据 (操作系统常用顺序)
- 高位/高字节从 低地址 开始放 : 12 23 56 78
- 即鸡蛋从大的一头敲开蛋壳 Big-Endian
"字节序0 是个什么鬼? : https://zhuanlan.zhihu.com/p/21388517
~~详情参考：详解大端模式和小端模式~~

解法

// 函数声明
bool isLittleEndian() {
    unsigned short data = 0x1122;
    return 0x22 == *((unsigned char*)&data);
}

// 测试代码
v(isLittleEndian()) // 运行在 MBP 的 macOS 上。

# 输出
isLittleEndian()  =  1

数值交换

交换两个变量的数值

// 函数声明：方法 0 - 借助临时变量
void swap0(int &x, int &y) {
    int tmp = x;
    x = y;
    y = x;
}

现在要求：在不使用第三个变量的情况下，实现两个变量的数值交换。

// 函数声明：方法 1 - 加减法
void swap1(int &x, iny &y) {
    x = x + y;  //  原理：
    y = x - y;  //  = (x + y) - y = x
    x = x - y;  //  = (x + y) - x = y
}

利用「加减」来交换变量的方法已经很巧妙了
可是当 x + y 的值超出 int 能表示的数值范围（溢出）时，会出错

// 函数声明：方法 2 - 位操作
void swap2(int &x, int &y) {
    //  因为 x ^ x = 0，0 ^ x = x 且 x ^ y ^ z = x ^ z ^ y（交换率）
    x = x ^ y;  //  所以：
    y = x ^ y;  //  = (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x
    x = x ^ y;  //  = (x ^ y) ^ x = (x ^ x) ^ y = 0 ^ y = y
}

利用更精妙的「位操作」方法，可以完美解决这个问题！
而且还特别好记，因为每一步都是 x ^ y

// 测试代码
x = 12;
y = 34;
l("initial state")
v(x)
v(y)
swap0(x, y);
l("after swap0()")
v(x)
v(y)
swap1(x, y);
l("after swap1()")
v(x)
v(y)
swap2(x, y);
l("after swap2()")
v(x)
v(y)

# 输出
initial state
    x  =  12
    y  =  34
after swap0()
    x  =  34
    y  =  12
after swap1()
    x  =  12
    y  =  34
after swap2()
    x  =  34
    y  =  12

但是我们必须要知道：在其它语言里，有更直接的变量交换方法。

// 在 Python 中变量的方法
x = 12
y = 34
x, y = y, x // 一定程度上解放了脑力
print(x, y)

# 输出
34 12

代码文件

程序源文件附件

CMakeLists.txt
print_tools.h
main.cpp

发到七牛云存储之后，才想起来用 GitHubGist 更方便:

cpp_macro_and_bit_operations。

后记

重做这些老题目，需要不到一整天的时间；但是将这些解答输出成本文，却需要超过一天。于是，我面临这样一个纠结的问题：从个人角度来看，到底值不值得将它们写成博文？

其实，在写本文之前、思考解题的过程中，我已经写了足以让自己理解、可用于复习的相关笔记和代码。如果要写这样一篇博文，当然要以「别人也能看得懂」为标准来认真地写，写得足够条理清晰。这样一来，就比写个人笔记更费神费时得多了。

当然，写作的过程中，我复习了相关的知识点，再一次理清了自己的思路，增进了理解（还给他人分享了经验）。但是，我与其付出整整一天的时间和精力去复习总结这些内容，好像还不如继续深入学习其它知识。

我纠结了。根据以往经验，我倾向于认为：不值得这么做。至少不应该急着写。应该隔一段时间，遗忘曲线下行之后再写，可以更好地增进记忆效果了。

这次就算了。接下来，我要试着一直学下去，先不写总结归纳的文章，看学习效果是不是更好。

吐槽：这种「自学」方面的实验，本来学生时代就该做了。如果当年一早搞清楚怎样的学习方法更适合自己，然后又快又好地进步，或许现在就不会活得那么窘迫了。

提醒自己：不要再埋怨了，不要埋怨，不要埋怨……

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

macro-n-bit-operations.md

macro-n-bit-operations.md

C++ 宏定义与位操作

宏定义

Print

数值的大小关系

数值的 sign

unsigned 数值类型

int 变量的 bytes

宏定义语法 `##`

位操作

int 整型数值

移位求积

2 的幂

求负数

求平均值

求绝对值

多少个 bit 为 1

相邻 bit 不同时为 1

不用 `+` 的加法

不用 `*` 的乘法

大小端

数值交换

代码文件

后记

Files

macro-n-bit-operations.md

Latest commit

History

macro-n-bit-operations.md

File metadata and controls

C++ 宏定义与位操作

宏定义

Print

数值的大小关系

数值的 sign

unsigned 数值类型

int 变量的 bytes

宏定义语法 ##

位操作

int 整型数值

移位求积

2 的幂

求负数

求平均值

求绝对值

多少个 bit 为 1

相邻 bit 不同时为 1

不用 + 的加法

不用 * 的乘法

大小端

数值交换

代码文件

后记

宏定义语法 `##`

不用 `+` 的加法

不用 `*` 的乘法