【题目集1】找不重复的数字，模拟实现aoti,宏实现offsetof

找不重复的数字

题目连接

一个数组中只有两个数字只出现一次，其他的数字都是出现两次，编写一个函数找出这两个只出现一次的数字的函数。

这道题的具体思路就是用异或的思想来解决。

什么是异或：

对于两个数字，相同为0，相异为1

异或的性质：

1. 交换律： a ^ b ^ c == a ^ c ^ b
2. 任何数与0异或都得任何数
3. 相同的数异或为0c

1. 看到上面3个关于异或的性质，是不是就明白了将数组中的所有的数字相互异或，最终得到的结果就是剩下的那两个数字异或的结果。我们还要明白只要不相同的两个数字异或，异或的结果的二进制数字里面一定存在1.
2. 接着我们根据这个1的位数，将这个数组分成两组，相同的数字分在一组，对于那两个不同的数字，肯定也会分在不同的组内

1. 最后我们只需要将这两组数据分别异或0，最后留下来的数字就是我们要找的两个数字。

代码如下：

#include <stdio.h>
int main() {
    int arr[] = {1, 2, 1, 3, 4, 4, 5, 7, 7,6};
    int len = sizeof(arr) / sizeof(arr[0]);
    int ret = 0;
    for(int i = 0; i < len; i ++) {
        ret ^= arr[i];
    }
    printf("%d \n", ret);
    //ret就是5^6的结果，二进制中一定有1
    //计算ret的第几位是1
    int pos = 0;
    for(int i = 0; i < 32; i ++) {
        if(((ret >> i) & 1) == 1) {
            pos = i;
            break;
        }
    }
    //ret的第pos位是1
    //把arr数组中的每个元素的pos位为1的数字异或在一起
    int num1 = 0;
    int num2 = 0;
    for(int i = 0; i < len; i ++) {
        if(((arr[i] >> pos) & 1) == 1) {
            num1 ^= arr[i];
        }else {
            num2 ^= arr[i];
        }
    }
    printf("%d %d ", num1, num2);
    return 0;
}

明白了这个题之后，我们以后遇到找数组中只出现一次的数字是不是就有一个非常高效的思路了那

模拟实现aoti函数

这个函数的主要功能就是将字符串的数字转换为数字。

#define  _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <ctype.h>
//
//my_atoi(NULL)//异常
//my_atoi("")//异常
//my_atoi("    +123")//正常
//my_atoi("-123")//正常
//my_atoi("123abc")//异常
//my_atoi("1111111111111111111111111")//异常
//my_atoi("-1111111111111111111111111")//异常
enum Status {
  VALID,
  INVALID
};
enum Status status = INVALID;
int my_aoti(char* str) {
  if (str == NULL) {
    return 0;
  }
  if (*str == '\0') {
    return 0;
  }
  //空白字符
  while (isspace(*str)) {
    str++;
  }
  int flag = 1;
  if (*str == '+') {
    flag = 1;
    str++;
  }
  else if (*str == '-') {
    flag = -1;
    str++;
  }
  //处理数字字符
  long long ret = 0;
  while (isdigit(*str)) {
    ret = ret * 10 + flag * (*str - '0');
    if (ret < INT_MIN || ret > INT_MAX) {
      return 0;
    }
    str++;
  }
  if (*str == '\0') {
    status = VALID;
    return (int)ret;
  }
  else {
    status = VALID;
    return (int)ret;
  }
}
int main() {
  //我们首先要有能力解决上面的几个异常
  int ret = my_aoti("123");
  if (status = VALID) {
    printf("非法的转换：%d", ret);
  }
  else {
    printf("合法的转换：%d", ret);
  }
}

用宏来实现offsetof函数

#include <stdio.h>
#include <stdlib.h>
struct S {
  char a;
  int b;
  char c;
};
#define OFFSTOF(s_type, m_name)  ((int)&((s_type*)0)->m_name)
int main() {
  printf("%d\n", OFFSTOF(struct S, a));
  printf("%d\n", OFFSTOF(struct S, b));
  printf("%d\n", OFFSTOF(struct S, c));
}