C语言位运算的使用算法问题案例

题目描述

小明接到字节跳动的笔试通知，其中有一道算法题目是：有11个整数，其中有5个整数各出现2次，1个整数出现了1次，请找出这个出现1次的整数。测试数据为{32,-1,0,32,100,66,66,-7,100,0,-1}。小明知道要定义一个一维数组，并将这11个整数初始化赋值给这个数组的每一个元素。请你在小明的想法的基础上，编写程序完成这道面试题目的要求。将程序代码复制粘贴到答题区，可以尝试运用位运算知识。
位运算知识提示:
(1)相同为0，不同为1，即1^1=0， 0^0=0， 0^1=1
(2)任何一个数和0按位异或就是其自身。例如：3^0=3；0000 0011 ^ 0000 0000 = 0000 0011

案例代码

你可以使用位运算中的异或（XOR）操作来解决这个问题。异或操作满足结合律和交换律，且一个数与0异或的结果为它本身。

以下是使用位运算解决这道题目的示例代码：

#include <stdio.h>

int findSingleNumber(int arr[], int length) {
    int result = 0;
    for (int i = 0; i < length; i++) {
        result ^= arr[i];
    }
    return result;
}

int main() {
    int arr[] = {32, -1, 0, 32, 100, 66, 66, -7, 100, 0, -1};
    int length = sizeof(arr) / sizeof(arr[0]);

    int singleNumber = findSingleNumber(arr, length);
    printf("The number that appears only once is: %d\n", singleNumber);

    return 0;
}

在上述代码中，我们定义了一个函数findSingleNumber，该函数接受一个整数数组和数组长度作为参数，并返回只出现一次的整数。通过遍历数组中的每个元素，将它们进行异或操作，最终得到的结果就是只出现一次的整数。

在main函数中，我们定义了测试数据的数组arr，并计算出数组的长度。然后调用findSingleNumber函数来找到只出现一次的整数，并将结果打印输出。

运行以上代码，输出结果为：

The number that appears only once is: -7

可以看到，只出现一次的整数是-7。

这个算法的时间复杂度为O(n)，其中n是数组的长度。由于只使用了常数额外空间，因此空间复杂度为O(1)。