#面试题#三进制异或

68 阅读 0 评论 45 点赞

我是靠谱客的博主要减肥花瓣，最近开发中收集的这篇文章主要介绍#面试题#三进制异或，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#面试题#数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。

分析：

假设该题目修改为：除了某一个数字x之外，其他数字都出现了两次，而x出现了一次。则可以把所有数字直接求异或，最终的结果就是x。这个很好理解。

而该题目是其他数字都出现了三次，可以想到三进制异或运算。其实异或运算的本质就是求和 % base。比如 1 ^ 1 = 0 其实就是 (1+1) % 2 = 0。因此只要按位求和，最后再将每位结果模除 3，再转换为二进制即是答案x。

代码如下：

#include 
   
   
    
    
using namespace std;
int main() {
    int a[100] = {0};
    int num;
    int i;
    while (cin >> num) {
        i = 0;
        while (num) {
            a[i++] += num & 1;  // the last num of base2 num
            num >>= 1;
        }
    }
    int x = 0;
    for (i = 99; i >= 0; i--) {
        if (a[i] > 0) break; //find the highest position
    }
    for (; i >= 0; i--) {
        if (a[i] % 3 != 0) {
            x += (1<