C语言需要掌握的基础知识点之位运算

位运算是在二进制位级别上直接操作数据的技术。C语言提供了丰富的位运算符，这些运算符在系统编程、嵌入式开发、性能优化等领域有广泛应用。

位运算的基本概念

位运算直接对整数在内存中的二进制位进行操作。C语言提供了6种位运算符，用于处理二进制数据。

位运算符详解

按位与（&）

#include <stdio.h>

void bitwiseAND() {
    printf("=== 按位与 (&) ===\n");
    
    unsigned int a = 0b1100;  // 12
    unsigned int b = 0b1010;  // 10
    
    printf("a = %u (二进制: 1100)\n", a);
    printf("b = %u (二进制: 1010)\n", b);
    printf("a & b = %u (二进制: 1000)\n", a & b);
    
    // 实际应用：检查特定位
    unsigned int flags = 0b10110101;
    unsigned int mask = 0b00010000;  // 检查第4位
    
    if (flags & mask) {
        printf("第4位是1\n");
    } else {
        printf("第4位是0\n");
    }
    
    // 实际应用：清除特定位
    unsigned int value = 0b11111111;
    unsigned int clearMask = 0b11110111;  // 清除第3位
    
    printf("清除前: %u\n", value);
    value &= clearMask;
    printf("清除后: %u\n", value);
}

按位或（|）

#include <stdio.h>

void bitwiseOR() {
    printf("\n=== 按位或 (|) ===\n");
    
    unsigned int a = 0b1100;  // 12
    unsigned int b = 0b1010;  // 10
    
    printf("a = %u (二进制: 1100)\n", a);
    printf("b = %u (二进制: 1010)\n", b);
    printf("a | b = %u (二进制: 1110)\n", a | b);
    
    // 实际应用：设置特定位
    unsigned int value = 0b00000000;
    unsigned int setMask = 0b00010000;  // 设置第4位
    
    printf("设置前: %u\n", value);
    value |= setMask;
    printf("设置后: %u\n", value);
    
    // 实际应用：合并多个标志
    unsigned int readPermission = 0b00000100;
    unsigned int writePermission = 0b00000010;
    unsigned int executePermission = 0b00000001;
    
    unsigned int fullPermissions = readPermission | writePermission | executePermission;
    printf("完整权限: %u (二进制: %03b)\n", fullPermissions, fullPermissions);
}

按位异或（^）

#include <stdio.h>

void bitwiseXOR() {
    printf("\n=== 按位异或 (^) ===\n");
    
    unsigned int a = 0b1100;  // 12
    unsigned int b = 0b1010;  // 10
    
    printf("a = %u (二进制: 1100)\n", a);
    printf("b = %u (二进制: 1010)\n", b);
    printf("a ^ b = %u (二进制: 0110)\n", a ^ b);
    
    // 实际应用：切换特定位
    unsigned int value = 0b10101010;
    unsigned int toggleMask = 0b00001111;  // 切换低4位
    
    printf("切换前: %u (二进制: 10101010)\n", value);
    value ^= toggleMask;
    printf("切换后: %u (二进制: 10100101)\n", value);
    
    // 实际应用：交换两个变量的值（不使用临时变量）
    int x = 10, y = 20;
    printf("交换前: x = %d, y = %d\n", x, y);
    
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
    
    printf("交换后: x = %d, y = %d\n", x, y);
}

按位取反（~）

#include <stdio.h>

void bitwiseNOT() {
    printf("\n=== 按位取反 (~) ===\n");
    
    unsigned int a = 0b00001111;  // 15
    
    printf("a = %u (二进制: 00001111)\n", a);
    printf("~a = %u (二进制: 11110000)\n", ~a);
    
    // 注意：结果取决于数据类型的大小
    unsigned char b = 0b00001111;  // 15
    printf("b = %u (二进制: 00001111)\n", b);
    printf("~b = %u (二进制: 11110000)\n", (unsigned char)~b);
    
    // 实际应用：创建掩码
    unsigned int mask = ~0;  // 所有位都是1
    printf("全1掩码: %u\n", mask);
    
    // 创建特定长度的掩码
    unsigned int low4bits = (1 << 4) - 1;  // 00001111
    printf("低4位掩码: %u\n", low4bits);
}

左移（<<）

#include <stdio.h>

void leftShift() {
    printf("\n=== 左移 (<<) ===\n");
    
    unsigned int a = 0b00000011;  // 3
    
    printf("a = %u (二进制: 00000011)\n", a);
    printf("a << 1 = %u (二进制: 00000110)\n", a << 1);
    printf("a << 2 = %u (二进制: 00001100)\n", a << 2);
    printf("a << 3 = %u (二进制: 00011000)\n", a << 3);
    
    // 实际应用：快速乘以2的幂
    int number = 7;
    printf("%d * 2 = %d\n", number, number << 1);
    printf("%d * 4 = %d\n", number, number << 2);
    printf("%d * 8 = %d\n", number, number << 3);
    
    // 实际应用：设置特定位
    unsigned int flags = 0;
    int bitPosition = 3;
    
    flags |= (1 << bitPosition);  // 设置第3位
    printf("设置第%d位后: %u\n", bitPosition, flags);
}

右移（>>）

#include <stdio.h>

void rightShift() {
    printf("\n=== 右移 (>>) ===\n");
    
    unsigned int a = 0b00011000;  // 24
    
    printf("a = %u (二进制: 00011000)\n", a);
    printf("a >> 1 = %u (二进制: 00001100)\n", a >> 1);
    printf("a >> 2 = %u (二进制: 00000110)\n", a >> 2);
    printf("a >> 3 = %u (二进制: 00000011)\n", a >> 3);
    
    // 实际应用：快速除以2的幂
    int number = 24;
    printf("%d / 2 = %d\n", number, number >> 1);
    printf("%d / 4 = %d\n", number, number >> 2);
    printf("%d / 8 = %d\n", number, number >> 3);
    
    // 注意：有符号数的右移（算术右移 vs 逻辑右移）
    int signedNum = -8;
    unsigned int unsignedNum = -8;
    
    printf("有符号数 -8 >> 1 = %d\n", signedNum >> 1);
    printf("无符号数 -8 >> 1 = %u\n", unsignedNum >> 1);
    
    // 实际应用：提取特定位
    unsigned int value = 0b10101010;
    int bitPosition = 5;
    int bitValue = (value >> bitPosition) & 1;
    
    printf("第%d位的值: %d\n", bitPosition, bitValue);
}

位运算的实用技巧

检查奇偶性

#include <stdio.h>

void checkParity() {
    printf("\n=== 检查奇偶性 ===\n");
    
    int numbers[] = {1, 2, 3, 4, 5, 10, 15, 20};
    int count = sizeof(numbers) / sizeof(numbers[0]);
    
    for (int i = 0; i < count; i++) {
        if (numbers[i] & 1) {
            printf("%d 是奇数\n", numbers[i]);
        } else {
            printf("%d 是偶数\n", numbers[i]);
        }
    }
}

判断2的幂

#include <stdio.h>
#include <stdbool.h>

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

void checkPowerOfTwo() {
    printf("\n=== 判断2的幂 ===\n");
    
    int numbers[] = {1, 2, 3, 4, 8, 16, 32, 64, 100, 128};
    int count = sizeof(numbers) / sizeof(numbers[0]);
    
    for (int i = 0; i < count; i++) {
        printf("%d %s2的幂\n", numbers[i], isPowerOfTwo(numbers[i]) ? "是" : "不是");
    }
}

计算二进制中1的个数

#include <stdio.h>

// 方法1：逐位检查
int countBits1(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// 方法2：Brian Kernighan算法
int countBits2(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

void countOnes() {
    printf("\n=== 计算二进制中1的个数 ===\n");
    
    int numbers[] = {0, 1, 2, 3, 7, 15, 255, 1023};
    int count = sizeof(numbers) / sizeof(numbers[0]);
    
    for (int i = 0; i < count; i++) {
        printf("数字 %d: 方法1 -> %d个1, 方法2 -> %d个1\n", 
               numbers[i], countBits1(numbers[i]), countBits2(numbers[i]));
    }
}

交换特定位

#include <stdio.h>

// 交换第i位和第j位
unsigned int swapBits(unsigned int n, int i, int j) {
    // 检查第i位和第j位是否相同
    if (((n >> i) & 1) != ((n >> j) & 1)) {
        // 创建掩码，只切换第i位和第j位
        unsigned int mask = (1 << i) | (1 << j);
        n ^= mask;
    }
    return n;
}

void demonstrateSwapBits() {
    printf("\n=== 交换特定位 ===\n");
    
    unsigned int num = 0b10101010;  // 170
    printf("原数字: %u (二进制: ", num);
    for (int i = 7; i >= 0; i--) {
        printf("%d", (num >> i) & 1);
    }
    printf(")\n");
    
    num = swapBits(num, 1, 5);
    printf("交换第1位和第5位后: %u (二进制: ", num);
    for (int i = 7; i >= 0; i--) {
        printf("%d", (num >> i) & 1);
    }
    printf(")\n");
}

位字段（Bit Fields）

#include <stdio.h>

// 使用位字段定义紧凑的数据结构
struct FilePermissions {
    unsigned int read : 1;     // 1位
    unsigned int write : 1;    // 1位
    unsigned int execute : 1;  // 1位
    unsigned int reserved : 5; // 5位
};

struct RGBColor {
    unsigned int red : 5;      // 5位 (0-31)
    unsigned int green : 6;    // 6位 (0-63)
    unsigned int blue : 5;     // 5位 (0-31)
};

void bitFieldsDemo() {
    printf("\n=== 位字段演示 ===\n");
    
    struct FilePermissions perm;
    perm.read = 1;
    perm.write = 0;
    perm.execute = 1;
    perm.reserved = 0;
    
    printf("文件权限: 读=%d, 写=%d, 执行=%d\n", 
           perm.read, perm.write, perm.execute);
    printf("结构体大小: %zu 字节\n", sizeof(perm));
    
    struct RGBColor color;
    color.red = 31;    // 最大红色
    color.green = 63;  // 最大绿色
    color.blue = 0;    // 无蓝色
    
    printf("RGB颜色: R=%d, G=%d, B=%d\n", color.red, color.green, color.blue);
    printf("结构体大小: %zu 字节\n", sizeof(color));
}

位运算在标志位中的应用

#include <stdio.h>

// 定义标志位常量
#define FLAG_READ    (1 << 0)  // 00000001
#define FLAG_WRITE   (1 << 1)  // 00000010
#define FLAG_EXECUTE (1 << 2)  // 00000100
#define FLAG_HIDDEN  (1 << 3)  // 00001000
#define FLAG_SYSTEM  (1 << 4)  // 00010000

void flagOperations() {
    printf("\n=== 标志位操作 ===\n");
    
    unsigned int flags = 0;
    
    // 设置标志
    flags |= FLAG_READ | FLAG_WRITE | FLAG_HIDDEN;
    printf("设置读、写、隐藏标志后: 0x%02X\n", flags);
    
    // 检查标志
    if (flags & FLAG_READ) {
        printf("具有读权限\n");
    }
    if (flags & FLAG_WRITE) {
        printf("具有写权限\n");
    }
    if (!(flags & FLAG_EXECUTE)) {
        printf("没有执行权限\n");
    }
    
    // 切换标志
    flags ^= FLAG_HIDDEN;  // 切换隐藏标志
    printf("切换隐藏标志后: 0x%02X\n", flags);
    
    // 清除标志
    flags &= ~FLAG_WRITE;  // 清除写标志
    printf("清除写标志后: 0x%02X\n", flags);
    
    // 检查多个标志
    if ((flags & (FLAG_READ | FLAG_WRITE)) == FLAG_READ) {
        printf("只有读权限，没有写权限\n");
    }
}

位运算在加密中的应用

#include <stdio.h>

// 简单的异或加密
void xorEncrypt(char *data, int length, char key) {
    for (int i = 0; i < length; i++) {
        data[i] ^= key;
    }
}

// 位旋转函数
unsigned int rotateLeft(unsigned int value, int shift) {
    return (value << shift) | (value >> (32 - shift));
}

unsigned int rotateRight(unsigned int value, int shift) {
    return (value >> shift) | (value << (32 - shift));
}

void encryptionDemo() {
    printf("\n=== 位运算在加密中的应用 ===\n");
    
    // 异或加密演示
    char message[] = "Hello, World!";
    char key = 0x55;
    
    printf("原消息: %s\n", message);
    
    xorEncrypt(message, sizeof(message) - 1, key);
    printf("加密后: %s\n", message);
    
    xorEncrypt(message, sizeof(message) - 1, key);
    printf("解密后: %s\n", message);
    
    // 位旋转演示
    unsigned int num = 0x12345678;
    printf("原数字: 0x%08X\n", num);
    printf("左旋转4位: 0x%08X\n", rotateLeft(num, 4));
    printf("右旋转4位: 0x%08X\n", rotateRight(num, 4));
}

位运算的性能优化

#include <stdio.h>
#include <time.h>

// 传统方法计算2的n次方
long long powerTraditional(int n) {
    long long result = 1;
    for (int i = 0; i < n; i++) {
        result *= 2;
    }
    return result;
}

// 使用位运算计算2的n次方
long long powerBitwise(int n) {
    return 1LL << n;
}

void performanceComparison() {
    printf("\n=== 位运算性能比较 ===\n");
    
    clock_t start, end;
    long long result;
    int n = 30;
    
    // 测试传统方法
    start = clock();
    result = powerTraditional(n);
    end = clock();
    printf("传统方法: 2^%d = %lld, 时间: %f 微秒\n", 
           n, result, (double)(end - start) / CLOCKS_PER_SEC * 1000000);
    
    // 测试位运算方法
    start = clock();
    result = powerBitwise(n);
    end = clock();
    printf("位运算方法: 2^%d = %lld, 时间: %f 微秒\n", 
           n, result, (double)(end - start) / CLOCKS_PER_SEC * 1000000);
}

实用的位运算函数库

#include <stdio.h>
#include <stdbool.h>

// 位运算工具函数库
typedef unsigned int uint;

// 设置特定位
uint setBit(uint num, int pos) {
    return num | (1 << pos);
}

// 清除特定位
uint clearBit(uint num, int pos) {
    return num & ~(1 << pos);
}

// 切换特定位
uint toggleBit(uint num, int pos) {
    return num ^ (1 << pos);
}

// 检查特定位
bool checkBit(uint num, int pos) {
    return (num >> pos) & 1;
}

// 获取最低位的1的位置
int getLowestSetBit(uint num) {
    if (num == 0) return -1;
    return __builtin_ffs(num) - 1;  // GCC内置函数
}

// 计算前导零的个数
int countLeadingZeros(uint num) {
    if (num == 0) return 32;
    return __builtin_clz(num);  // GCC内置函数
}

// 打印二进制表示
void printBinary(uint num) {
    for (int i = 31; i >= 0; i--) {
        printf("%d", (num >> i) & 1);
        if (i % 4 == 0 && i != 0) printf(" ");
    }
    printf("\n");
}

void bitUtilityDemo() {
    printf("\n=== 位运算工具函数演示 ===\n");
    
    uint num = 0b1010;  // 10
    
    printf("原数字: %u, 二进制: ", num);
    printBinary(num);
    
    num = setBit(num, 2);
    printf("设置第2位后: %u, 二进制: ", num);
    printBinary(num);
    
    num = clearBit(num, 3);
    printf("清除第3位后: %u, 二进制: ", num);
    printBinary(num);
    
    num = toggleBit(num, 1);
    printf("切换第1位后: %u, 二进制: ", num);
    printBinary(num);
    
    printf("第0位是: %d\n", checkBit(num, 0));
    printf("最低位1的位置: %d\n", getLowestSetBit(num));
    printf("前导零的个数: %d\n", countLeadingZeros(num));
}

位运算的注意事项

运算符优先级

#include <stdio.h>

void operatorPrecedence() {
    printf("\n=== 位运算符优先级 ===\n");
    
    int a = 1, b = 2, c = 3;
    
    // 常见的优先级错误
    int result1 = a & b == 2;   // 相当于 a & (b == 2)
    int result2 = (a & b) == 2; // 正确的写法
    
    printf("a & b == 2 = %d (可能不是期望的结果)\n", result1);
    printf("(a & b) == 2 = %d\n", result2);
    
    // 推荐的写法：使用括号明确优先级
    int x = 5, y = 3;
    int and_result = x & y;
    int or_result = x | y;
    int xor_result = x ^ y;
    
    printf("%d & %d = %d\n", x, y, and_result);
    printf("%d | %d = %d\n", x, y, or_result);
    printf("%d ^ %d = %d\n", x, y, xor_result);
}

有符号数的位运算

#include <stdio.h>

void signedBitOperations() {
    printf("\n=== 有符号数的位运算 ===\n");
    
    int positive = 5;    // 00000101
    int negative = -5;   // 补码表示
    
    printf("正数 %d: ", positive);
    for (int i = 31; i >= 0; i--) {
        printf("%d", (positive >> i) & 1);
    }
    printf("\n");
    
    printf("负数 %d: ", negative);
    for (int i = 31; i >= 0; i--) {
        printf("%d", (negative >> i) & 1);
    }
    printf("\n");
    
    // 右移有符号数的行为
    printf("有符号数右移:\n");
    printf("%d >> 1 = %d\n", positive, positive >> 1);
    printf("%d >> 1 = %d (算术右移)\n", negative, negative >> 1);
    
    // 转换为无符号数进行逻辑右移
    unsigned int unsigned_negative = (unsigned int)negative;
    printf("无符号数右移: %u >> 1 = %u (逻辑右移)\n", 
           unsigned_negative, unsigned_negative >> 1);
}