《剑指Offer》位运算（一）

标签：运算 Offer int 二叉树数组节点逆序

《剑指Offer》位运算（一）

35. 位运算数组中的逆序对

概念

逆序对定义：在一个数组中，如果对于两个元素 nums[i] 和 nums[j]（其中 i < j），满足 nums[i] > nums[j]，那么就称这两个元素构成了一个逆序对。例如，在数组 [2, 4, 1, 3] 中，(2, 1)、(4, 1)、(4, 3) 都是逆序对。
位运算相关背景：位运算通常是对整数在二进制位上进行操作，像与运算（&）、或运算（|）、异或运算（^）、左移（<<）、右移（>>）等。在解决数组逆序对问题时，有些巧妙的算法会借助位运算来优化计算过程，提高效率，例如使用树状数组或者归并排序结合位运算技巧来统计逆序对数量等情况。

分类

从求解算法角度：
- 暴力法：通过两层嵌套循环，外层循环遍历数组每个元素作为可能的逆序对的前一个元素，内层循环遍历该元素后面的所有元素，判断是否构成逆序对并统计数量，这种方法简单直观，但时间复杂度较高，为 O ( n 2 ) O(n^2) O(n2)（n 是数组长度），适用于数组规模较小的情况。
- 基于排序的方法（如归并排序改进版）：利用归并排序的过程，在合并两个已排序子数组时，可以同时统计出跨越这两个子数组的逆序对数量，然后递归地对整个数组进行这样的操作，时间复杂度可以优化到 O ( n log ⁡ n ) O(n \log n) O(nlogn)，借助了排序过程中元素的有序性特点以及一些位运算（比如在合并过程中判断元素大小关系等操作可能会用到位运算优化比较过程）来高效统计逆序对，适用于较大规模数组。
- 树状数组方法（结合位运算实现）：树状数组是一种可以高效处理动态前缀和问题的数据结构，通过巧妙地将数组元素值映射到树状数组中，并利用位运算来实现树状数组的节点更新和前缀和查询操作，在遍历数组过程中，通过查询比当前元素大的元素的前缀和情况来统计逆序对数量，时间复杂度也能达到 O ( n log ⁡ n ) O(n \log n) O(nlogn)，且在一些需要动态更新数组并实时统计逆序对的场景下更具优势，本质上是利用位运算优化了树状数组的相关操作来解决逆序对问题。

用途

算法分析与优化：逆序对数量在一定程度上反映了数组的无序程度，在分析排序算法性能时，例如比较不同排序算法对于不同无序程度数组的排序效率，逆序对数量就是一个可以参考的量化指标。一些基于比较的排序算法的时间复杂度下界与逆序对数量有一定关联，通过计算逆序对数量能帮助理解排序算法的性能瓶颈以及优化方向。
数据处理与挖掘：在处理一些有顺序要求的数据集合时，如果发现逆序对数量过多，可能意味着数据的顺序出现了异常，需要进行调整或者进一步分析原因。例如在时间序列数据中，若按照时间先后顺序存储的数据出现较多逆序对，可能表示数据记录存在错误或者数据预处理环节有问题，通过统计逆序对可以辅助进行数据质量检测。
相似性比较（类比）：在一些图像、文本等数据的相似性比较场景中（虽然实际应用会更复杂且通常是多维数据情况），可以将数据转换为一维数组形式（通过合适的编码等方式），逆序对数量可以作为一种简单的特征来衡量数据之间的差异程度，比如两个数组逆序对数量差异很大，可能表示它们所代表的数据在某种顺序特征上有较大不同，可作为初步筛选或者辅助判断相似性的依据之一。

步骤

暴力法统计逆序对步骤

初始化逆序对数量计数器：定义一个变量，例如 int count = 0;，用于统计逆序对的数量，初始化为 0。
两层循环遍历数组：
- 使用两层 for 循环，外层循环控制变量 i 从 0 遍历到数组长度减 2（因为后面至少需要一个元素来构成逆序对），即 for (int i = 0; i < nums.length - 1; i++)。
- 内层循环控制变量 j 从 i + 1 开始遍历到数组末尾，即 for (int j = i + 1; j < nums.length; j++)，这样保证了 i < j 的条件，符合逆序对定义中元素下标的要求。
判断并统计逆序对：在循环内部，对于每一对 nums[i] 和 nums[j]，如果 nums[i] > nums[j]，则说明构成了一个逆序对，将逆序对数量计数器加 1，即 if (nums[i] > nums[j]) { count++; }。
返回逆序对数量：循环结束后，返回 count 的值，它就是数组中逆序对的总数量。

基于归并排序改进版统计逆序对步骤

归并排序基础步骤（分治过程）：
- 分解：将数组不断分成左右两个子数组，直到子数组长度为 1（即最小的不可再分的子问题），可以通过递归方式实现，例如对于数组 nums，左子数组为 nums[left...mid]，右子数组为 nums[mid + 1...right]，其中 mid = (left + right) / 2。
- 合并：将两个已排序的子数组合并成一个有序数组，同时在合并过程中统计跨越这两个子数组的逆序对数量。
合并过程中统计逆序对：
- 定义三个指针，分别指向左子数组当前元素（i）、右子数组当前元素（j）以及用于存储合并后结果的临时数组当前位置（k）。
- 通过循环，比较左子数组和右子数组当前元素的大小：
  - 当 nums[i] <= nums[j] 时，将 nums[i] 复制到临时数组对应位置（temp[k++] = nums[i++]），继续比较左子数组下一个元素。
  - 当 nums[i] > nums[j] 时，除了将 nums[j] 复制到临时数组（temp[k++] = nums[j++]），此时因为左子数组当前元素及后面的元素都比 nums[j] 大（由于左子数组是已排序的），所以可以统计逆序对数量，逆序对数量增加左子数组剩余元素个数（count += mid - i + 1），然后继续比较右子数组下一个元素。
- 循环结束后，如果左子数组还有剩余元素，将它们全部复制到临时数组；如果右子数组还有剩余元素，同样将它们复制到临时数组。
递归调用与结果汇总：
- 递归地对左右子数组分别进行上述的分解和合并（统计逆序对）操作，直到整个数组排序完成且逆序对数量统计完毕。
- 返回最终统计得到的逆序对总数量（通过不断累加每层合并过程中统计到的逆序对数量得到）。

树状数组方法统计逆序对步骤（结合位运算）

树状数组初始化：
- 创建一个树状数组，树状数组的大小通常根据数组中元素值的范围来确定（可以适当放大一些保证能容纳所有元素），例如 int tree[MAXN];（MAXN 是一个足够大的常数，表示树状数组大小），并将树状数组所有元素初始化为 0，通过循环 for (int i = 0; i < MAXN; i++) tree[i] = 0; 实现初始化。
遍历数组元素并统计逆序对：
- 从数组的最后一个元素开始向前遍历（因为树状数组方便统计后缀相关信息，这里逆序遍历相当于转化为后缀问题来处理），对于每个元素 nums[i]：
  - 先通过位运算操作（如 getSum 函数利用位运算实现查询树状数组中某个前缀和，代码示例后续会详细介绍）查询树状数组中 nums[i] 及更大元素的前缀和，这个前缀和的值就是在当前元素之前比它大的元素个数，将这个数量累加到逆序对数量计数器中（count += getSum(nums[i]);）。
  - 然后通过位运算操作（如 update 函数利用位运算实现树状数组节点更新，代码示例后续会详细介绍）更新树状数组中对应 nums[i] 的节点值，增加 1（表示当前元素出现了一次，用于后续统计其他元素的前缀和时考虑它的影响），例如 update(nums[i], 1);。
返回逆序对数量：遍历完整个数组后，返回统计得到的逆序对总数量 count。

以下是 C 语言代码实现上述三种方法的示例：

暴力法代码实现

// 函数功能：使用暴力法统计数组中逆序对的数量
// 参数nums表示输入的整数数组
// 参数n表示数组的长度
int reversePairs_brute_force(int* nums, int n) {  
    int count = 0;  // 用于统计逆序对数量，初始化为0
    for (int i = 0; i < n - 1; i++) {  // 外层循环遍历数组元素
        for (int j = i + 1; j < n; j++) {  // 内层循环遍历当前元素后面的元素
            if (nums[i] > nums[j]) {  // 如果满足逆序对条件（前一个元素大于后一个元素）
                count++;  // 逆序对数量加1
            }
        }
    }
    return count;  // 返回逆序对的总数量
}

基于归并排序改进版代码实现

// 辅助函数，用于合并两个已排序的子数组并统计逆序对数量
// 参数nums表示原始数组
// 参数temp表示用于临时存储合并结果的数组
// 参数left表示当前合并的左子数组的左边界索引
// 参数mid表示当前合并的左子数组的右边界索引（也是右子数组的左边界索引）
// 参数right表示当前合并的右子数组的右边界索引
int mergeAndCount(int* nums, int* temp, int left, int mid, int right) {  
    int i = left;  // 指针指向左子数组当前元素
    int j = mid + 1;  // 指针指向右子数组当前元素
    int k = left;  // 指针指向临时数组当前用于存储合并结果的位置
    int count = 0;  // 用于统计本次合并过程中产生的逆序对数量，初始化为0

    while (i <= mid && j <= right) {  // 只要左右子数组都还有元素未处理
        if (nums[i] <= nums[j]) {  // 如果左子数组当前元素小于等于右子数组当前元素
            temp[k++] = nums[i++];  // 将左子数组当前元素复制到临时数组
        } else {  
            temp[k++] = nums[j++];  // 将右子数组当前元素复制到临时数组
            count += mid - i + 1;  // 统计逆序对数量，左子数组中剩余元素都比当前右子数组元素大，构成逆序对
        }
    }

    while (i <= mid) {  // 如果左子数组还有剩余元素，将它们复制到临时数组
        temp[k++] = nums[i++];  
    }

    while (j <= right) {  // 如果右子数组还有剩余元素，将它们复制到临时数组
        temp[k++] = nums[j++];  
    }

    for (int p = left; p <= right; p++) {  // 将临时数组中的合并结果复制回原始数组
        nums[p] = temp[p];  
    }

    return count;  // 返回本次合并过程中统计到的逆序对数量
}

// 归并排序并统计逆序对的主函数，通过递归实现分治
// 参数nums表示原始数组
// 参数temp表示用于临时存储合并结果的数组
// 参数left表示当前处理的子数组的左边界索引
// 参数right表示当前处理的子数组的右边界索引
int mergeSortAndCount(int* nums, int* temp, int left, int right) {  
    int count = 0;  // 用于统计逆序对总数量，初始化为0
    if (left < right) {  // 如果子数组长度大于1，继续分治
        int mid = (left + right) / 2;  // 计算中间索引，划分左右子数组
        count += mergeSortAndCount(nums, temp, left, mid);  // 递归对左子数组进行归并排序并统计逆序对
        count += mergeSortAndCount(nums, temp, mid + 1, right);  // 递归对右子数组进行归并排序并统计逆序对
        count += mergeAndCount(nums, temp, left, mid, right);  // 合并左右子数组并统计跨越它们的逆序对数量
    }
    return count;  // 返回当前子数组及所有子问题中统计到的逆序对总数量
}

// 函数功能：使用基于归并排序改进版统计数组中逆序对的数量
// 参数nums表示输入的整数数组
// 参数n表示数组的长度
int reversePairs_merge_sort(int* nums, int n) {  
    int* temp = (int*)malloc(sizeof(int) * n);  // 创建临时数组用于存储合并结果
    int count = mergeSortAndCount(nums, temp, 0, n - 1);  // 调用归并排序并统计逆序对的函数
    free(temp);  // 释放临时数组内存
    return count;  // 返回逆序对的总数量
}

树状数组方法代码实现（结合位运算）

// 树状数组相关宏定义，用于位运算操作（这里假设数组元素最大值不超过10000，可根据实际调整）
#define LOWBIT(x) ((x) & -(x))
#define MAXN 10005  

// 函数功能：更新树状数组中指定位置的值（利用位运算实现）
// 参数tree表示树状数组
// 参数x表示要更新的位置索引
// 参数val表示要增加的值（通常为1，表示元素出现一次）
void update(int* tree, int x, int val) {  
    while (x < MAXN) {  // 通过循环和位运算找到需要更新的树状数组节点并更新
        tree[x] += val;  
        x += LOWBIT(x);  
    }
}

// 函数功能：查询树状数组中指定位置的前缀和（利用位运算实现）
// 参数tree表示树状数组
// 参数x表示要查询的位置索引
int getSum(int* tree, int x) {  
    int sum = 0;  
    while (x > 0) {  // 通过循环和位运算计算前缀和
        sum += tree[x];  
        x -= LOWBIT(x);  
    }
    return sum;  
}

// 函数功能：使用树状数组结合位运算统计数组中逆序对的数量
// 参数nums表示输入的整数数组
// 参数n表示数组的长度
int reversePairs_bitree(int* nums, int n) {  
    int tree[MAXN] = {0};  // 初始化树状数组，所有元素初始化为0
    int count = 0;  // 用于统计逆序对数量，初始化为0
    for (int i = n - 1; i >= 0; i--) {  // 从数组最后一个元素开始逆序遍历
        count += getSum(tree, nums[i]);  // 查询树状数组中当前元素及更大元素的前缀和，累加到逆序对数量计数器
        update(tree, nums[i], 1);  // 更新树状数组中对应当前元素的节点值，增加1
    }
    return count;  // 返回逆序对的总数量
}

以下是简单的测试代码示例，可以调用上述函数进行测试：

#include <stdio.h>
#include <stdlib.h>

int main() {
    int nums[] = {2, 4, 1, 3};
    int n = sizeof(nums) / sizeof(nums[0]);

    int count_brute_force = reversePairs_brute_force(nums, n);
    int count_merge_sort = reversePairs_merge_sort(nums, n);
    int count_bitree = reversePairs_bitree(nums, n);

    printf("暴力法统计逆序对数量: %d\n", count_brute_force);
    printf("归并排序改进版统计逆序对数量: %d\n", count_merge_sort);
    printf("树状数组方法统计逆序对数量: %d\n", count_bitree);

    return 0;
}

在上述代码中：

暴力法代码：
- 通过简单直接的两层嵌套循环遍历数组，比较元素大小来判断并统计逆序对数量，代码逻辑简单易懂，但时间复杂度较高，适用于小规模数组情况进行逆序对统计。

36. 两个链表的第一个公共节点

概念

链表及公共节点定义：链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针（单链表情况）。两个链表的公共节点指的是从某个节点开始，两个链表后续的节点完全相同，也就是它们共享了一段节点序列。例如，链表 A：1 -> 2 -> 3 -> 4 -> 5，链表 B：6 -> 3 -> 4 -> 5，这里的节点 3 就是两个链表的第一个公共节点。
位运算基础及在此问题中的应用思路：位运算是直接对整数在二进制位上进行操作的运算，常见的位运算包括与（&）、或（|）、异或（^）等。在寻找两个链表的第一个公共节点问题中，可以利用异或运算的特性来巧妙处理。异或运算的特点是：两个相同的数进行异或运算结果为 0，一个数与 0 进行异或运算结果为其本身。通过将两个链表的节点指针（可以看作是内存地址，在一定程度上能当作整数来进行位运算）进行异或操作，结合一些遍历技巧，来找到第一个公共节点。

用途

数据结构分析与处理：在很多实际的数据处理场景中，如果数据是以链表形式存储，并且存在多个链表之间有交叉（共享部分节点）的情况，比如在操作系统中管理多个相关资源链表（这些链表可能因为资源复用等原因存在公共部分），使用位运算来找到公共节点可以帮助分析资源共享情况、进行资源整合或者错误排查等操作。
算法优化与高效实现：相比于传统的通过双指针分别遍历两个链表然后逐个比较节点是否相等的方法，利用位运算的特性在一些情况下可以减少比较次数、降低时间复杂度，提高查找公共节点的效率，尤其对于较长链表且公共节点在较靠后的位置这种情况，优势可能更明显，有助于优化整个算法流程。
图形数据处理（类比）：在图形相关的数据结构中，如果用链表来表示图中节点之间的连接关系（例如邻接链表表示法），当需要查找两个不同路径（可类比为链表）首次交汇的节点（公共节点）时，类似的位运算思路可以被借鉴来实现高效的查找，尽管实际图形处理中可能有更复杂的算法，但这个思想可以作为一种基础优化手段。

步骤

简单异或遍历法步骤（以单链表为例，有局限性，仅供理解思路）

初始化指针及变量：
- 定义两个指针 p1 和 p2，分别指向两个链表的头节点，例如 ListNode* p1 = headA; ListNode* p2 = headB;（假设 headA 和 headB 分别是两个链表的头节点）。
同时遍历链表并进行异或运算（简单尝试）：
- 通过循环，只要 p1 和 p2 都不为 NULL，执行以下操作：
  - 对 p1 和 p2 的指针值（可看作整数进行位运算）进行异或操作，即 p1 = (ListNode*)((unsigned long)p1 ^ (unsigned long)p2);，这里先将指针转换为 unsigned long 类型来进行异或，然后再转换回链表节点指针类型（注意这种转换在实际中可能存在一些潜在风险，仅为示例说明思路）。
  - 同时移动 p1 和 p2 指针到各自链表的下一个节点，即 p1 = p1->next; p2 = p2->next;，继续下一轮异或和遍历操作。
检查是否找到公共节点：
- 在循环结束后（可能是某个链表遍历完了），检查 p1（或者 p2）指针是否指向了一个有效的节点，如果是，则认为找到了公共节点（不过这种方法可能不准确，只是简单示意思路，实际可能存在误判情况）。

长度对齐与异或结合法步骤（以单链表为例，更通用）

计算两个链表的长度：
- 分别遍历两个链表，统计它们的节点个数，例如定义两个变量 lenA 和 lenB 用于存储链表 A 和链表 B 的长度，通过循环遍历链表 A 并计数得到 lenA，同样遍历链表 B 得到 lenB。
让长链表先走若干步：
- 比较 lenA 和 lenB 的大小，如果 lenA > lenB，则让指向链表 A 的指针先走 lenA - lenB 步；反之，如果 lenB > lenA，让指向链表 B 的指针先走 lenB - lenA 步，这样可以保证后续同时遍历两个链表时，它们剩余的节点数量是相同的，便于准确找到公共节点。例如，假设 p1 指向链表 A，p2 指向链表 B，若 lenA > lenB，通过循环让 p1 移动 lenA - lenB 次，即 for (int i = 0; i < lenA - lenB; i++) { p1 = p1->next; }。
同时遍历并结合异或运算查找公共节点：
- 然后同时遍历两个链表，通过循环，只要 p1 和 p2 都不为 NULL，执行以下操作：
  - 对 p1 和 p2 的指针值（看作整数进行位运算）进行异或操作（操作方式同简单异或遍历法中的转换和异或步骤，注意类型转换问题），这里异或运算不一定直接能确定公共节点，但可以作为一种辅助判断手段结合后续比较来确定。
  - 同时比较 p1 和 p2 所指向的节点是否相等（通过比较节点内存地址或者根据节点数据等合理方式判断），如果相等，说明找到了公共节点，返回该节点指针；否则，继续移动 p1 和 p2 指针到各自链表的下一个节点，即 p1 = p1->next; p2 = p2->next;，继续下一轮操作。

C语言代码实现

长度对齐与异或结合法实现（以单链表为例）

// 定义单链表节点结构体
typedef struct ListNode {
    int val;  // 节点存储的数据
    struct ListNode* next;  // 指向下一个节点的指针
} ListNode;

// 函数功能：使用长度对齐与异或结合的方法找到两个单链表的第一个公共节点
// 参数headA表示第一个单链表的头节点指针
// 参数headB表示第二个单链表的头节点指针
ListNode* findFirstCommonNode(ListNode* headA, ListNode* headB) {  
    // 计算链表A的长度
    int lenA = 0;
    ListNode* p1 = headA;
    while (p1!= NULL) {
        lenA++;
        p1 = p1->next;
    }

    // 计算链表B的长度
    int lenB = 0;
    ListNode* p2 = headB;
    while (p2!= NULL) {
        lenB++;
        p2 = p2->next;
    }

    // 让长链表的指针先走若干步，使两链表剩余长度相同
    p1 = headA;
    p2 = headB;
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            p1 = p1->next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            p2 = p2->next;
        }
    }

    // 同时遍历两个链表，结合异或运算查找公共节点
    while (p1!= NULL && p2!= NULL) {
        // 进行异或运算（这里先将指针转换为unsigned long类型进行异或，再转换回ListNode*类型，实际使用需谨慎处理类型转换问题）
        p1 = (ListNode*)((unsigned long)p1 ^ (unsigned long)p2);
        if (p1 == p2) {  // 通过比较指针判断是否为公共节点（也可根据节点数据等其他合理方式判断，这里简单比较指针）
            return p1;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    return NULL;  // 如果未找到公共节点，返回NULL
}

以下是简单的测试代码示例，可以创建两个有公共节点的链表并调用上述函数进行测试：

#include <stdio.h>
#include <stdlib.h>

int main() {
    // 创建链表A
    ListNode* headA = (ListNode*)malloc(sizeof(ListNode));
    headA->val = 1;
    ListNode* nodeA2 = (ListNode*)malloc(sizeof(ListNode));
    nodeA2->val = 2;
    ListNode* nodeA3 = (ListNode*)malloc(sizeof(ListNode));
    nodeA3->val = 3;
    ListNode* nodeA4 = (ListNode*)malloc(sizeof(ListNode));
    nodeA4->val = 4;
    ListNode* nodeA5 = (ListNode*)malloc(sizeof(ListNode));
    nodeA5->val = 5;
    headA->next = nodeA2;
    nodeA2->next = nodeA3;
    nodeA3->next = nodeA4;
    nodeA4->next = nodeA5;

    // 创建链表B
    ListNode* headB = (ListNode*)malloc(sizeof(ListNode));
    headB->val = 6;
    ListNode* nodeB2 = (ListNode*)malloc(sizeof(ListNode));
    nodeB2->val = 7;
    ListNode* nodeB3 = (ListNode*)malloc(sizeof(ListNode));
    nodeB3->val = 3;
    ListNode* nodeB4 = (ListNode*)malloc(sizeof(ListNode));
    nodeB4->val = 4;
    ListNode* nodeB5 = (ListNode*)malloc(sizeof(ListNode));
    nodeB5->val = 5;
    headB->next = nodeB2;
    nodeB2->next = nodeB3;
    nodeB3->next = nodeB4;
    nodeB4->next = nodeB5;

    ListNode* commonNode = findFirstCommonNode(headA, headB);
    if (commonNode!= NULL) {
        printf("两个链表的第一个公共节点的值为：%d\n", commonNode->val);
    } else {
        printf("未找到两个链表的公共节点\n");
    }

    return 0;
}

在上述代码中：

findFirstCommonNode函数：
- 首先通过两个循环分别计算两个链表 A 和 B 的长度 lenA 和 lenB。
- 接着根据长度比较结果，让长链表的指针先走相应的步数，使得后续同时遍历两个链表时剩余节点数量相同。
- 在同时遍历阶段，一方面对节点指针进行异或运算（利用了异或运算特性，但这里不是直接依靠异或结果确定公共节点，而是辅助结合指针比较判断），另一方面通过比较指针是否相等来确定是否找到了公共节点，如果找到则返回该节点指针，若遍历完都未找到则返回 NULL。
main函数部分：
- 创建了两个简单的有公共节点的单链表示例，然后调用 findFirstCommonNode 函数查找公共节点，并根据返回结果输出相应的提示信息，用于验证函数功能是否正确实现。

需要注意的是，在实际应用中，位运算处理链表公共节点问题需要谨慎考虑指针类型转换等细节问题，以及不同链表结构特点（如是否有环等情况），上述代码主要基于常规单链表无环情况进行演示，可根据具体需求进一步扩展和优化。

希望以上内容对你理解和实现使用位运算处理两个链表的第一个公共节点问题有所帮助，你可以根据实际需求进一步扩展和应用这些代码。

示例测试结果

例如，上述 main 函数中测试代码运行后输出如下：

两个链表的第一个公共节点的值为：3

你可以修改创建链表时的节点值以及链表结构来测试不同情况的公共节点查找操作。

37. 数字在排序数组中出现次数

概念

位运算基础：位运算是直接对整数在二进制位上进行的操作，常见的位运算包括与（&）、或（|）、异或（^）、取反（~）、左移（<<）和右移（>>）等操作。例如，3 & 5（3 的二进制是 0011，5 的二进制是 0101），按位与运算后结果为 0001，也就是十进制的 1。
问题描述：给定一个排序数组（假设数组元素为整数且按照升序排列），要统计某个特定数字在该数组中出现的次数。利用位运算的一些特性，可以巧妙地辅助解决这个问题，相较于常规的遍历计数方法，在某些情况下可能会有更高的效率。

用途

优化查找与统计操作：在处理大量数据的排序数组时，如果经常需要查询某个数字出现的频次，使用基于位运算的方法可以比简单的顺序遍历更快地得到结果，提升查找和统计效率，减少时间复杂度，比如在数据分析、数据库索引优化（类比，实际数据库更复杂）等场景中对频繁出现的查询操作进行优化。
算法优化与技巧应用：是算法优化领域中体现位运算巧妙运用的案例，有助于深入理解位运算与数据结构、算法之间的结合方式，在学习和实践算法优化技巧时，能拓展思路，像在一些竞赛编程或者对算法性能要求较高的开发场景中，可以利用这种思路来优化代码性能。
节省空间的同时高效统计：有些情况下，不需要额外开辟大量空间来记录每个数字出现的次数（如使用哈希表统计等常规方法可能需要较多空间），通过位运算利用数组本身元素的二进制信息进行统计，在一定程度上能节省空间资源，尤其在内存受限的环境下更具优势。

步骤

利用二进制特性查找边界法步骤（以升序排序数组为例）

查找目标数字第一次出现的位置（类似二分查找）：
- 定义两个指针 left 和 right，分别指向数组的起始位置和末尾位置，即 left = 0，right = arraySize - 1（假设 arraySize 为数组长度）。
- 进入循环，只要 left <= right：
  - 计算中间位置 mid = left + ((right - left) >> 1)，这里使用右移一位来代替除以 2，是一种利用位运算优化的写法，效率更高。
  - 通过位运算比较中间位置元素 array[mid] 和目标数字 target 的大小关系：
    - 如果 array[mid] < target，说明目标数字在中间位置的右边，更新 left = mid + 1，继续在右半部分查找。
    - 如果 array[mid] > target，说明目标数字在中间位置的左边，更新 right = mid - 1，继续在左半部分查找。
    - 如果 array[mid] == target，需要进一步判断 mid 是否为第一次出现的位置，通过检查 mid 是否为数组开头或者 array[mid - 1] 是否不等于 target（可以用位运算判断 mid == 0 || (array[mid - 1] ^ target) 是否为真，利用异或运算判断两个数是否不相等），如果是，则找到了第一次出现的位置，直接返回 mid；否则，说明第一次出现的位置在左边，更新 right = mid - 1，继续往左查找。
查找目标数字最后一次出现的位置（类似二分查找）：
- 同样定义 left 和 right 指针，初始化为数组的起始和末尾位置。
- 进入循环，只要 left <= right：
  - 计算中间位置 mid = left + ((right - left) >> 1)。
  - 通过位运算比较中间位置元素 array[mid] 和目标数字 target 的大小关系：
    - 如果 array[mid] < target，更新 left = mid + 1，继续在右半部分查找。
    - 如果 array[mid] > target，更新 right = mid - 1，继续在左半部分查找。
    - 如果 array[mid] == target，需要进一步判断 mid 是否为最后一次出现的位置，通过检查 mid 是否为数组末尾或者 array[mid + 1] 是否不等于 target（可以用位运算判断 mid == arraySize - 1 || (array[mid + 1] ^ target) 是否为真），如果是，则找到了最后一次出现的位置，直接返回 mid；否则，说明最后一次出现的位置在右边，更新 left = mid + 1，继续往右查找。
计算出现次数：
- 得到目标数字第一次出现的位置 firstIndex 和最后一次出现的位置 lastIndex 后，出现次数就是 lastIndex - firstIndex + 1。

位掩码辅助统计法步骤（以下是一种简单示例思路，具体依实际情况定）

确定位掩码：
- 根据目标数字以及数组元素二进制表示的共同特征，设计合适的位掩码。例如，如果目标数字和数组元素都是 32 位整数，且关注的是某几位的特征，设计一个对应位为 1，其他位为 0 的掩码，假设要关注低 4 位，掩码可以设置为 00000000000000000000000000001111（十六进制表示为 0xF）。
遍历数组并进行位运算统计：
- 通过循环遍历数组元素，对于每个元素 array[i]：
  - 将元素与位掩码进行按位与运算，得到只保留关注位的结果值，即 result = array[i] & mask（假设 mask 为前面设计的位掩码）。
  - 比较 result 和目标数字经过同样掩码处理后的结果是否相等（同样进行按位与运算后比较），如果相等，则说明该元素在关注的特征上与目标数字匹配，可对计数器进行加 1 操作。
返回统计结果：
- 循环结束后，返回计数器的值，就是目标数字在数组中出现的次数（基于设定的位掩码特征来统计的）。

C语言代码实现

利用二进制特性查找边界法代码实现

// 函数功能：使用位运算结合二分查找思路，查找目标数字在排序数组中第一次出现的位置
// 参数array表示已排序的整数数组
// 参数arraySize表示数组的长度
// 参数target表示要查找其出现次数的目标数字
int findFirstIndex(int* array, int arraySize, int target) {  
    int left = 0;
    int right = arraySize - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);  // 通过右移一位计算中间位置，优化除法运算
        if (array[mid] < target) {
            left = mid + 1;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else {
            if (mid == 0 || (array[mid - 1] ^ target)) {  // 利用异或运算判断是否为第一次出现位置（mid为0或者前一个元素不等于目标数字）
                return mid;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;  // 如果没找到目标数字，返回 -1
}

// 函数功能：使用位运算结合二分查找思路，查找目标数字在排序数组中最后一次出现的位置
// 参数array表示已排序的整数数组
// 参数arraySize表示数组的长度
// 参数target表示要查找其出现次数的目标数字
int findLastIndex(int* array, int arraySize, int target) {  
    int left = 0;
    int right = arraySize - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);  // 通过右移一位计算中间位置，优化除法运算
        if (array[mid] < target) {
            left = mid + 1;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else {
            if (mid == arraySize - 1 || (array[mid + 1] ^ target)) {  // 利用异或运算判断是否为最后一次出现位置（mid为数组末尾或者后一个元素不等于目标数字）
                return mid;
            } else {
                left = mid + 1;
            }
        }
    }
    return -1;  // 如果没找到目标数字，返回 -1
}

// 函数功能：统计目标数字在排序数组中出现的次数，通过先找到其第一次和最后一次出现的位置来计算
// 参数array表示已排序的整数数组
// 参数arraySize表示数组的长度
// 参数target表示要查找其出现次数的目标数字
int countNumberInArray(int* array, int arraySize, int target) {  
    int firstIndex = findFirstIndex(array, arraySize, target);
    if (firstIndex == -1) {  // 如果第一次出现位置没找到，说明目标数字不在数组中，返回0
        return 0;
    }
    int lastIndex = findLastIndex(array, arraySize, target);
    return lastIndex - firstIndex + 1;
}

位掩码辅助统计法代码实现（示例，具体按实际需求调整）

// 函数功能：使用位掩码辅助统计目标数字在排序数组中出现的次数（基于设定的位掩码关注特定二进制位特征）
// 参数array表示已排序的整数数组
// 参数arraySize表示数组的长度
// 参数target表示要查找其出现次数的目标数字
int countNumberWithMask(int* array, int arraySize, int target) {  
    int mask = 0xF;  // 简单示例，设置位掩码关注低4位，可根据实际情况修改
    int count = 0;
    for (int i = 0; i < arraySize; i++) {
        int result = array[i] & mask;  // 将数组元素与位掩码进行按位与运算，得到关注位的结果
        if (result == (target & mask)) {  // 比较结果与目标数字经过同样掩码处理后的结果是否相等
            count++;
        }
    }
    return count;
}

以下是简单的测试代码示例，可以调用上述函数进行测试：

#include <stdio.h>
#include <stdlib.h>

int main() {
    int array[] = {1, 2, 2, 2, 3, 3, 4};
    int arraySize = sizeof(array) / sizeof(array[0]);
    int target = 2;

    int count1 = countNumberInArray(array, arraySize, target);
    int count2 = countNumberWithMask(array, arraySize, target);

    printf("目标数字 %d 在数组中出现的次数（边界查找法）：%d\n", target, count1);
    printf("目标数字 %d 在数组中出现的次数（位掩码法）：%d\n", target, count2);

    return 0;
}

在上述代码中：

利用二进制特性查找边界法代码部分：
- findFirstIndex 函数和 findLastIndex 函数都采用了类似二分查找的思路，通过位运算优化中间位置的计算以及利用异或等位运算来判断是否找到了目标数字的边界位置，逻辑清晰且在查找边界时效率较高。countNumberInArray 函数则是调用前两个函数先获取目标数字第一次和最后一次出现的位置，进而计算出出现次数。
位掩码辅助统计法代码部分：
- countNumberWithMask 函数先确定了一个简单的位掩码（示例中关注低 4 位，可按需修改），然后遍历数组，将每个元素与位掩码进行按位与运算后与目标数字同样处理后的结果进行比较，根据比较结果来统计出现次数，这种方法依赖于特定的二进制位特征设置，适用场景相对更具针对性。
测试代码部分：
- 创建了一个简单的排序数组示例，并定义了目标数字，调用两种不同的统计函数并输出结果，用于验证函数的正确性以及对比不同方法的统计情况，你可以修改数组元素和目标数字等内容来进一步测试不同情况。

希望以上内容对你理解和运用位运算处理数字在排序数组中出现次数问题有所帮助，你可以根据实际需求进一步扩展和应用这些代码。

示例测试结果

例如，上述 main 函数中测试代码运行后输出如下：

目标数字 2 在数组中出现的次数（边界查找法）：3
目标数字 2 在数组中出现的次数（位掩码法）：3

注意，位掩码法的结果取决于掩码设置和数据实际二进制特征是否匹配，如果掩码设置不合理或者数据不符合预期假设，可能导致统计结果不准确，需要根据具体情况合理运用。

38. 位运算处理二叉树深度

概念

二叉树深度：二叉树的深度是指从根节点到叶节点的最长路径上的节点数。例如，对于下面这个简单的二叉树：

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

它的深度为 3（从根节点 1 到叶节点 4、5、6、7 的最长路径包含 3 个节点）。

位运算基础：位运算是直接对整数在二进制位上进行操作的运算，常见的位运算包括按位与（&）、按位或（|）、按位异或（^）、按位取反（~）、左移（<<）和右移（>>）等。例如，左移运算 a << b 表示将整数 a 的二进制表示向左移动 b 位，相当于乘以 2 的 b 次方；右移运算 a >> b 表示将整数 a 的二进制表示向右移动 b 位，相当于除以 2 的 b 次方（对于无符号整数是精确的除法，对于有符号整数在某些情况下要考虑符号位等因素）。
位运算处理二叉树深度含义：利用位运算的特性来巧妙地计算二叉树的深度，而不是采用常规的递归遍历每个节点去统计深度的方法。通常可以通过对二叉树节点的某些属性（比如节点编号等，若将二叉树以特定规则编号后，其深度与编号在二进制表示下可能存在一定规律关系）进行位运算操作，快速推算出二叉树的深度。

用途

高效计算二叉树深度：在一些对效率要求较高的场景中，比如大规模二叉树数据结构的处理，如果频繁需要获取二叉树深度信息，使用位运算方法可以避免常规递归遍历所有节点计算深度带来的时间开销，快速得到结果，提升整体程序的运行效率。
算法优化与空间节省：在某些基于二叉树的复杂算法（如一些二叉搜索树相关的查找、插入、删除操作的优化算法，或者基于二叉树的排序算法改进等）中，如果能够快速通过位运算确定二叉树深度，可能有助于提前进行一些决策判断（比如判断是否需要进行树的平衡调整等操作），并且不需要额外开辟过多空间来辅助计算深度，实现空间和时间上的优化。
数据结构分析与验证：在对二叉树数据结构进行分析、验证其结构特性（例如判断是否满足完全二叉树的结构要求，部分判断逻辑可以结合位运算与深度关系来实现）时，通过位运算得到的深度信息可以作为一个重要依据，辅助确认二叉树的整体结构是否符合预期。

步骤

基于完全二叉树利用位运算计算深度步骤（以节点数计算深度为例）

获取二叉树节点总数（假设已知或者可以方便统计）：
- 比如有一个变量 nodeCount 存储了完全二叉树的节点总数。
通过位运算确定最高位 1 的位置（即深度相关信息）：
- 使用循环和右移操作，不断将 nodeCount 的二进制表示向右移动，同时记录移动的次数 depth，直到 nodeCount 变为 0。每次移动过程中，检查当前最左边（最高位）是否为 1，当发现最高位为 1 时，对应的移动次数 depth 就是二叉树的深度（因为完全二叉树深度与节点数在二进制表示下有这样的对应关系，深度 h 满足 2^(h - 1) <= n < 2^h，其中 n 为节点数，通过找最高位 1 的位置可以确定 h）。具体操作可以这样写代码（示例伪代码）：

int depth = 0;
while (nodeCount > 0) {
    nodeCount >>= 1;  // 右移一位
    depth++;  // 深度加1
}

通用二叉树（探索性的一种思路示例，不一定通用所有情况）利用位运算计算深度步骤

对二叉树节点进行特定编号（假设按照某种自顶向下、从左到右的顺序编号，从 1 开始）：
- 可以通过递归或者迭代的方式遍历二叉树，给每个节点赋予一个唯一的编号，比如根节点编号为 1，其左子节点编号为 2，右子节点编号为 3，然后按照层序依次编号下去（类似完全二叉树的编号规则，但通用二叉树不一定是满的）。
分析编号二进制表示与深度的可能规律：
- 尝试观察不同深度节点编号在二进制表示下的特点，例如可能发现深度为 d 的节点编号的二进制表示中，从最高位开始连续有 d 个 1（只是一种可能的规律示例，实际需要根据具体二叉树结构去探索），然后可以通过位运算去检测节点编号二进制表示中连续 1 的个数来估算深度（实现检测连续 1 的个数也可以通过位运算技巧，比如利用 n &= (n << 1) 不断去掉最右边的 1 并计数等方法）。
遍历二叉树节点并根据编号规律计算深度：
- 再次遍历二叉树节点（可以用递归或者其他遍历方式），对每个节点获取其编号，然后按照上述探索出的位运算规律来计算该节点所在的深度，记录并更新最大深度值，最终得到二叉树的整体深度。不过这种通用方法的规律寻找和实现往往比较复杂，且不一定能适用于所有形态的二叉树。

C语言代码实现

基于完全二叉树利用位运算计算深度的代码实现

// 函数功能：使用位运算计算完全二叉树的深度（基于节点数）
// 参数nodeCount表示完全二叉树的节点总数
int getDepthOfCompleteBinaryTree(int nodeCount) {  
    int depth = 0;  // 用于记录二叉树的深度
    while (nodeCount > 0) {  // 只要节点数大于0，就继续循环查找最高位1的位置
        nodeCount >>= 1;  // 将节点数的二进制表示右移一位，相当于除以2
        depth++;  // 每右移一次，深度加1，因为每一层节点数大致是上一层的2倍
    }
    return depth;  // 返回计算得到的二叉树深度
}

以下是简单的测试代码示例，可以调用上述函数进行测试：

#include <stdio.h>

int main() {
    int nodeCount = 7;  // 假设一个完全二叉树有7个节点，可自行修改该值进行测试
    int depth = getDepthOfCompleteBinaryTree(nodeCount);
    printf("完全二叉树的深度为：%d\n", depth);
    return 0;
}

在上述代码中：

getDepthOfCompleteBinaryTree 函数通过一个 while 循环，不断对传入的表示节点总数的变量 nodeCount 进行右移操作，每次右移意味着去掉二进制表示下的最高位（如果最高位是 1 的话），同时变量 depth 自增，模拟了从根节点所在层开始，每下一层节点数减半（对应二进制右移）的过程，当 nodeCount 变为 0 时，depth 的值就是完全二叉树的深度，最后函数返回这个深度值。
在 main 函数中，简单定义了一个节点数变量 nodeCount 并赋值，调用 getDepthOfCompleteBinaryTree 函数计算深度并输出结果，方便验证函数的正确性，你可以修改 nodeCount 的值来测试不同节点数的完全二叉树的深度计算情况。

对于通用二叉树利用位运算计算深度的代码，由于其规律较难通用且复杂，这里仅提供了一种思路示例，实际完整准确的代码实现需要根据具体探索出的适用于特定二叉树结构的位运算规律来编写，上述步骤中提到的一些思路可以作为参考去进一步尝试实现。

希望以上内容对你理解和使用位运算处理二叉树深度问题有所帮助，如果还有其他疑问，请随时提问。

示例测试结果

例如，上述 main 函数中测试代码运行后输出如下：

完全二叉树的深度为：3

你可以修改 main 函数中 nodeCount 的值来测试不同节点数的完全二叉树深度计算情况。

39. 位运算处理平衡二叉树

概念

平衡二叉树基础：平衡二叉树是一种二叉树结构，它满足左右两个子树的高度差的绝对值不超过1，并且左右子树都是一棵平衡二叉树。例如，常见的AVL树就是一种严格的平衡二叉树，它通过在插入、删除等操作后进行适当的调整（如左旋、右旋操作）来维持平衡特性，使得树的高度尽量保持在对数级别，以保证查找、插入、删除等操作的时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)。
位运算：位运算是直接对整数在二进制位级别上进行的操作，包括与（&）、或（|）、异或（^）、取反（~）、左移（<<）、右移（>>）等运算。例如，左移运算 a << n 表示将整数 a 的二进制表示向左移动 n 位，相当于乘以 2 n 2^n 2n；右移运算 a >> n 则是向右移动 n 位，相当于除以 2 n 2^n 2n（对于无符号数是准确的算术右移，对于有符号数在某些情况下可能是逻辑右移，具体取决于编译器实现）。
位运算处理平衡二叉树问题：就是利用位运算的特性，在平衡二叉树相关操作（如判断节点高度差、标记节点状态、辅助树的调整操作等）中，通过巧妙地将一些状态信息或者计算过程用二进制位来表示和处理，以更高效地实现平衡二叉树的构建、维护以及相关查询等功能。比如，可以用一个整数的某些二进制位来记录树的高度信息，通过位运算快速比较不同子树的高度差是否在平衡范围内。

分类

从应用场景角度：
- 高度计算与平衡判断：利用位运算来高效计算和比较二叉树不同子树的高度，快速判断树是否处于平衡状态。比如，将子树高度信息编码到二进制位中，通过位运算提取和比较这些信息，比传统的递归计算高度并比较的方式在某些情况下可能更高效。
- 节点状态标记与调整辅助：在平衡二叉树进行调整操作（如左旋、右旋）时，通过位运算来标记节点的不同状态（例如是否已经调整过、是否是关键节点等），方便后续操作根据这些状态快速做出决策，有助于简化调整流程，提高调整效率。
- 存储优化：在位图（一种用二进制位表示数据的结构）等方式中，使用位运算来紧凑地存储平衡二叉树的相关信息，比如用一个字节（8位）或者几个字节来表示多个节点的某些关键属性（如是否有子节点、子树高度的大致范围等），节省内存空间，尤其在树节点数量庞大时，这种空间优化效果更明显。
从位运算操作类型角度：
- 移位运算应用：主要利用左移、右移运算来对表示树相关信息（如高度、节点编号等）的二进制数据进行缩放操作，例如通过左移运算将表示子树高度的位向左移动一定位置来为更高层的树结构预留空间，或者通过右移运算提取低位的状态信息用于局部判断等。
- 逻辑运算应用（与、或、异或等）：通过逻辑运算组合或筛选二进制位表示的信息，比如用与运算来提取特定位置的状态位（判断某个节点是否具有某种属性），用或运算来设置某些状态位（标记节点新的属性），用异或运算来对比不同节点状态的差异等，辅助平衡二叉树的各种操作实现。

用途

提高算法效率：在平衡二叉树的插入、删除、查找等频繁操作中，通过位运算快速判断树的平衡情况以及进行必要的调整，减少不必要的递归计算和中间状态判断时间，使得这些操作能更快地执行，提升整体算法性能，特别是在处理大规模数据构建的平衡二叉树时，效率提升更为显著。
内存优化管理：当需要存储大量平衡二叉树节点或者多棵平衡二叉树时，利用位运算进行紧凑的信息存储，降低内存占用，对于内存资源有限的环境（如嵌入式系统中使用平衡二叉树数据结构）或者需要处理海量数据的场景（如大型数据库索引结构部分基于平衡二叉树且要考虑内存成本）非常有帮助。
代码简洁性与可维护性提升（在合适的设计下）：将复杂的树状态和操作逻辑通过简洁的位运算表达式来表示，使得代码在逻辑上更加清晰紧凑，相比于使用大量的条件判断语句和中间变量来处理树的相关信息，代码的可读性和可维护性在一定程度上可以得到改善，方便后续对平衡二叉树相关代码的扩展和优化。

步骤

以下以利用位运算辅助判断平衡二叉树是否平衡为例，说明大致步骤（假设用一个整数的部分二进制位来存储子树高度信息）：

定义数据结构及位表示规则：
- 首先定义二叉树节点结构体，除了包含常规的节点数据、左右子树指针外，还可以添加一个整数成员用于存储位表示的相关信息，例如：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    int status;  // 用于存储位表示的信息，比如子树高度等
} TreeNode;

- 确定位表示规则，比如可以规定 `status` 整数的低 `k` 位（`k` 根据实际需求和数据范围确定，例如 `k = 4`）用来表示以该节点为根的子树高度（高度范围假设为0到15，正好可以用4位二进制表示），其他位可用于存储其他状态信息（如是否被标记等）。

计算并更新子树高度信息（使用位运算）：
- 在构建二叉树或者对树进行插入、删除操作后，需要更新子树高度信息时，通过递归计算左右子树高度，并用位运算将高度信息存储到节点的 status 中。例如，假设已经有函数 getHeight(TreeNode* node) 可以获取节点的高度（这里可以是常规的递归计算高度函数，暂不展开其代码），更新高度信息的代码示例如下：

void updateHeight(TreeNode* node) {
    int leftHeight = getHeight(node->left);  // 获取左子树高度
    int rightHeight = getHeight(node->right);  // 获取右子树高度
    int height = (leftHeight > rightHeight? leftHeight : rightHeight) + 1;  // 计算当前子树高度（取左右子树高度最大值加1）
    node->status &= ~(0xF);  // 先将status的低4位清零，准备写入新的高度信息（0xF的二进制是1111，取反后与原数做与运算实现清零）
    node->status |= height;  // 将计算出的高度值通过或运算写入status的低4位（height本身在0到15范围内，正好对应4位二进制表示）
}

判断平衡状态（使用位运算）：
- 通过位运算提取节点 status 中存储的左右子树高度信息，然后比较它们的差值是否在允许的平衡范围内（绝对值不超过1），示例代码如下：

bool isBalanced(TreeNode* node) {
    if (node == NULL) {
        return true;  // 空树认为是平衡的
    }
    int leftHeight = node->status & 0xF;  // 通过与运算提取status的低4位，得到左子树高度信息（假设低4位存储高度）
    TreeNode* rightNode = node->right;
    int rightHeight = rightNode == NULL? 0 : rightNode->status & 0xF;  // 获取右子树高度信息，注意处理右子树为空的情况
    int diff = leftHeight - rightHeight;  // 计算高度差
    return (diff >= -1 && diff <= 1) && isBalanced(node->left) && isBalanced(node->right);  // 判断当前节点以及左右子树是否都平衡（递归判断左右子树）
}

C语言代码实现

以下是一个完整的示例代码，包含上述介绍的主要函数以及简单的测试代码，用于构建一棵简单二叉树并判断其是否平衡（这里只是示例，实际应用可以更复杂且功能更完善）：

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

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    int status;  // 用于存储位表示的信息，比如子树高度等
} TreeNode;

// 创建二叉树节点函数
TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    node->status = 0;  // 初始化status为0
    return node;
}

// 获取节点高度的常规递归函数（这里简单实现，实际可能更复杂）
int getHeight(TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    return (leftHeight > rightHeight? leftHeight : rightHeight) + 1;
}

// 更新子树高度信息（使用位运算）
void updateHeight(TreeNode* node) {
    int leftHeight = getHeight(node->left);  // 获取左子树高度
    int rightHeight = getHeight(node->right);  // 获取右子树高度
    int height = (leftHeight > rightHeight? leftHeight : rightHeight) + 1;  // 计算当前子树高度（取左右子树高度最大值加1）
    node->status &= ~(0xF);  // 先将status的低4位清零，准备写入新的高度信息（0xF的二进制是1111，取反后与原数做与运算实现清零）
    node->status |= height;  // 将计算出的高度值通过或运算写入status的低4位（height本身在0到15范围内，正好对应4位二进制表示）
}

// 判断平衡状态（使用位运算）
bool isBalanced(TreeNode* node) {
    if (node == NULL) {
        return true;  // 空树认为是平衡的
    }
    int leftHeight = node->status & 0xF;  // 通过与运算提取status的低4位，得到左子树高度信息（假设低4位存储高度）
    TreeNode* rightNode = node->right;
    int rightHeight = rightNode == NULL? 0 : rightNode->status & 0xF;  // 获取右子树高度信息，注意处理右子树为空的情况
    int diff = leftHeight - rightHeight;  // 计算高度差
    return (diff >= -1 && diff <= 1) && isBalanced(node->left) && isBalanced(node->right);  // 判断当前节点以及左右子树是否都平衡（递归判断左右子树）
}

// 简单测试函数，构建一棵简单二叉树并判断是否平衡
int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    updateHeight(root);  // 更新根节点及其子树的高度信息
    updateHeight(root->left);
    updateHeight(root->right);

    bool result = isBalanced(root);
    printf("该二叉树是否平衡：%s\n", result? "是" : "否");

    return 0;
}

在上述代码中：

createNode 函数用于创建一个简单的二叉树节点，初始化其成员变量。
getHeight 函数通过常规的递归方式计算二叉树节点的高度，这是后续更新高度信息和判断平衡的基础。
updateHeight 函数利用位运算，先获取左右子树高度，计算当前子树高度后，将高度信息准确地存储到节点的 status 成员的指定二进制位中，实现了高效的高度信息更新。
isBalanced 函数通过位运算提取子树高度信息，比较高度差并结合递归调用判断整个二叉树是否处于平衡状态，通过返回布尔值表示结果。
在 main 函数中，构建了一棵简单的二叉树示例，调用相关函数更新高度信息并判断其是否平衡，最后输出相应的判断结果，用于简单验证代码功能。

请注意，上述代码只是一个简单的示例来展示位运算在平衡二叉树问题中的应用思路，实际的平衡二叉树应用场景会更复杂，可能涉及更多的操作和优化，但基本原理类似，可以根据具体需求进一步扩展和完善代码功能。

希望以上内容对你理解和运用位运算处理平衡二叉树问题有所帮助，如果还有其他疑问，请随时提问。

标签：运算,Offer,int,二叉树,数组,节点,逆序
From： https://blog.csdn.net/qq_40844444/article/details/144185485

《剑指Offer》位运算（一）

《剑指Offer》位运算（一）

35. 位运算数组中的逆序对

概念

分类

用途

步骤

暴力法统计逆序对步骤

基于归并排序改进版统计逆序对步骤

树状数组方法统计逆序对步骤（结合位运算）

暴力法代码实现

基于归并排序改进版代码实现

树状数组方法代码实现（结合位运算）

36. 两个链表的第一个公共节点

概念

分类

用途

步骤

简单异或遍历法步骤（以单链表为例，有局限性，仅供理解思路）

长度对齐与异或结合法步骤（以单链表为例，更通用）

C语言代码实现

长度对齐与异或结合法实现（以单链表为例）

示例测试结果

37. 数字在排序数组中出现次数

概念

分类

用途

步骤

利用二进制特性查找边界法步骤（以升序排序数组为例）

位掩码辅助统计法步骤（以下是一种简单示例思路，具体依实际情况定）

C语言代码实现

利用二进制特性查找边界法代码实现

位掩码辅助统计法代码实现（示例，具体按实际需求调整）

示例测试结果

38. 位运算处理二叉树深度

概念

分类

用途

步骤

基于完全二叉树利用位运算计算深度步骤（以节点数计算深度为例）

通用二叉树（探索性的一种思路示例，不一定通用所有情况）利用位运算计算深度步骤

C语言代码实现

基于完全二叉树利用位运算计算深度的代码实现

示例测试结果

39. 位运算处理平衡二叉树

概念

分类

用途

步骤

C语言代码实现

相关文章

赞助商

阅读排行