位算法-查找只出现一次的元素

一个数组里每个元素都出现 3 次,除了其中一个数字只出现 1 次,查找打印只出现一次的那个数字

[1,1,1,3]
3

[2,3,4,3,3,2,2]
4


算法1

基础知识:

x^x = 0
0^x = x

原理:

位出现1次的,存入 ones,位出现2次的存入twos,位出现3次的直接从 ones twos 里移除


linux c例子

#include <stdio.h> 

int getSingle(int arr[], int n) 
{
    int i;
    int ones = 0, twos = 0;

    int common_bit_mask;

    // Let us take the example of {3, 3, 2, 3} to understand this 
    for(i=0; i< n; i++ )
    {
        twos = twos | (ones & arr[i]);

        ones = ones ^ arr[i];

        //去掉公共位,即出现了3次
        common_bit_mask = ~(ones & twos);
        ones &= common_bit_mask;
        twos &= common_bit_mask;

    }
    return ones; 
}

int main() 
{ 
    int arr[] = {2,3,4,3,3,2,2}; 
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("The element with single occurrence is %d\n", getSingle(arr, n)); 
    return 0; 
}


算法2

就是把对应位相加余上3,不等于0的那个即为只出现1次

{5, 5, 5, 8}    101, 101, 101, 1000

Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0

Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0

Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0

Sum of fourth bits%3 = (1)%3 = 1

1000

#include <stdio.h> 
#define INT_SIZE 32 
  
int getSingle(int arr[], int n) 
{ 
    int result = 0; 
  
    int x, sum; 
    int i,j;

    for (i = 0; i < INT_SIZE; i++) 
    {
      sum = 0; 
      x = (1 << i); 
      for (j=0; j< n; j++ ) 
      { 
          if (arr[j] & x) 
            sum++; 
      } 
  
      if (sum % 3) 
        result |= x; 
    } 
  
    return result; 
} 
  
int main() 
{ 
    int arr[] = {7,12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printf("The element with single occurrence is %d\n", getSingle(arr, n));
    return 0; 
}


参考:

stackoverflow

geeksforgeeks

上一篇: 有限自动机
下一篇: 校验2个整数符号是否相同
作者邮箱: 203328517@qq.com