bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1 * Legal ops: ~ & * Max ops: 14 * Rating: 2

下面是一种实现方法：

int bitXor(int x, int y) {
    int a = x & ~y;
    int b = ~x & y;
    int result = ~(~a & ~b) & ~(a & b);
    return result;
}

这个方法的思路是，利用按位取反和按位与运算来实现按位异或运算。具体来说，先对 x 和 y 进行按位与运算和按位取反运算，得到 a 和 b，分别表示 x 和 y 中非重复的位。然后对 a 和 b 进行按位与运算和按位取反运算，最后得到的结果就是 x 和 y 进行按位异或运算的结果。

相关问题

如何在Legal ops: ~ & * 和 Max ops: 14条件下编码bitXor(int x, int y)

在Legal ops: ~ & * 和 Max ops: 14条件下，可以使用以下代码实现bitXor(int x, int y)函数：

int bitXor(int x, int y) {
  int a = x & y;
  int b = ~x & ~y;
  return ~(~a & ~b);
}

这里的思路是将x和y进行按位与运算得到a，表示x和y中二进制位均为1的位置。然后将x和y进行按位取反运算，再将结果进行按位与运算得到b，表示x和y中二进制位均为0的位置。最后将a和b进行按位取反运算并返回结果即可，表示x和y中二进制位不相同的位置。

CREATE OR REPLACE FUNCTION Murmurhash3(input_data VARCHAR2, seed NUMBER) RETURN NUMBER IS h NUMBER := seed; c1 NUMBER := 3458204593; -- 0xcc9e2d51 c2 NUMBER := 1735298763; -- 0x1b873593 r1 NUMBER := 15; r2 NUMBER := 13; m NUMBER := 5; n NUMBER := 364292196; -- 0xe6546b64 blkNums NUMBER := LENGTH(input_data) / 4; remaining_bytes VARCHAR2(4); k NUMBER := 0; res NUMBER := 0; BEGIN FOR i IN 0..blkNums-1 LOOP res := 0; FOR j IN 0..3 LOOP res := res + ASCII(SUBSTR(input_data, i*4+j+1, 1)) * POWER(2, (3-j)*8); END LOOP; res := res * c1; res := MOD(res, POWER(2, 32)); res := BITAND(res, POWER(2, 32)-1); res := res || 0; res := BITAND(res, POWER(2, 32)-1); res := BITAND(res * POWER(2, r1), POWER(2, 32)-1); res := res || 0; res := BITAND(res, POWER(2, 32)-1); res := BITAND(res * c2, POWER(2, 32)-1); res := res || 0; res := BITAND(res, POWER(2, 32)-1); h := BITAND(h*m + n, POWER(2, 32)-1); h := BITAND(h+res, POWER(2, 32)-1); END LOOP; remaining_bytes := SUBSTR(input_data, blkNums*4+1); FOR i IN 1..LENGTH(remaining_bytes) LOOP k := k + ASCII(SUBSTR(remaining_bytes, i, 1)) * POWER(2, (4-i)*8); END LOOP; k := k * c1; k := MOD(k, POWER(2, 32)); k := BITAND(k, POWER(2, 32)-1); k := BITAND(k * POWER(2, r1), POWER(2, 32)-1); k := BITAND(k * c2, POWER(2, 32)-1); k := BITAND(k || 0, POWER(2, 32)-1); h := BITXOR(h, k); h := BITXOR(h, LENGTH(input_data)); h := BITAND(h, POWER(2, 32)-1); h := BITAND(h XOR (h SHR 16), POWER(2, 32)-1); h := BITAND(h * 2246822507, POWER(2, 32)-1); h := BITAND(h XOR (h SHR 13), POWER(2, 32)-1); h := BITAND(h * 3226489909, POWER(2, 32)-1); h := BITAND(h XOR (h SHR 16), POWER(2, 32)-1); RETURN h; END; /

以上是一个 Oracle PL/SQL Function 函数的示例代码，实现了 MurmurHash3 哈希算法，以下是逐行解释：

- `CREATE OR REPLACE FUNCTION Murmurhash3(input_data VARCHAR2, seed NUMBER) RETURN NUMBER IS`：声明一个名为 `Murmurhash3` 的函数，它有两个参数，分别是 `input_data` 和 `seed`，返回值是一个数字。

- `h NUMBER := seed;`：初始化一个变量 `h`，赋值为 `seed`。

- `c1 NUMBER := 3458204593;`：初始化一个常量 `c1`，值为 `3458204593`。

- `c2 NUMBER := 1735298763;`：初始化一个常量 `c2`，值为 `1735298763`。

- `r1 NUMBER := 15;`：初始化一个常量 `r1`，值为 `15`。

- `r2 NUMBER := 13;`：初始化一个常量 `r2`，值为 `13`。

- `m NUMBER := 5;`：初始化一个常量 `m`，值为 `5`。

- `n NUMBER := 364292196;`：初始化一个常量 `n`，值为 `364292196`。

- `blkNums NUMBER := LENGTH(input_data) / 4;`：计算 `input_data` 的长度并除以 4，得到块数。

- `remaining_bytes VARCHAR2(4);`：声明一个变量 `remaining_bytes`，表示剩余未处理的字节数。

- `k NUMBER := 0;`：初始化一个变量 `k`，值为 `0`。

- `res NUMBER := 0;`：声明一个变量 `res`，表示哈希值。

- `FOR i IN 0..blkNums-1 LOOP`：循环处理每个数据块。

- `FOR j IN 0..3 LOOP`：循环处理每个字节。

- `res := res + ASCII(SUBSTR(input_data, i*4+j+1, 1)) * POWER(2, (3-j)*8);`：计算哈希值。

- `END LOOP;`：内层循环结束。

- `res := res * c1;`：乘以常量 `c1`。

- `res := MOD(res, POWER(2, 32));`：对 2^32 取模。

- `res := BITAND(res, POWER(2, 32)-1);`：按位与，清除高位。

- `res := res || 0;`：将结果转换为 32 位无符号整数。

- `res := BITAND(res, POWER(2, 32)-1);`：按位与，清除高位。

- `res := BITAND(res * POWER(2, r1), POWER(2, 32)-1);`：左移 r1 位，按位与，清除高位。

- `res := res || 0;`：将结果转换为 32 位无符号整数。

- `res := BITAND(res, POWER(2, 32)-1);`：按位与，清除高位。

- `res := BITAND(res * c2, POWER(2, 32)-1);`：乘以常量 `c2`，按位与，清除高位。

- `res := res || 0;`：将结果转换为 32 位无符号整数。

- `res := BITAND(res, POWER(2, 32)-1);`：按位与，清除高位。

- `h := BITAND(h*m + n, POWER(2, 32)-1);`：计算哈希值。

- `h := BITAND(h+res, POWER(2, 32)-1);`：计算哈希值。

- `END LOOP;`：外层循环结束。

- `remaining_bytes := SUBSTR(input_data, blkNums*4+1);`：获取剩余未处理的字节。

- `FOR i IN 1..LENGTH(remaining_bytes) LOOP`：循环处理剩余字节。

- `k := k + ASCII(SUBSTR(remaining_bytes, i, 1)) * POWER(2, (4-i)*8);`：计算哈希值。

- `END LOOP;`：循环结束。

- `k := k * c1;`：乘以常量 `c1`。

- `k := MOD(k, POWER(2, 32));`：对 2^32 取模。

- `k := BITAND(k, POWER(2, 32)-1);`：按位与，清除高位。

- `k := BITAND(k * POWER(2, r1), POWER(2, 32)-1);`：左移 r1 位，按位与，清除高位。

- `k := BITAND(k * c2, POWER(2, 32)-1);`：乘以常量 `c2`，按位与，清除高位。

- `k := BITAND(k || 0, POWER(2, 32)-1);`：将结果转换为 32 位无符号整数。

- `h := BITXOR(h, k);`：异或运算。

- `h := BITXOR(h, LENGTH(input_data));`：异或运算。

- `h := BITAND(h, POWER(2, 32)-1);`：按位与，清除高位。

- `h := BITAND(h XOR (h SHR 16), POWER(2, 32)-1);`：右移 16 位，按位异或，按位与，清除高位。

- `h := BITAND(h * 2246822507, POWER(2, 32)-1);`：乘以常量，按位与，清除高位。

- `h := BITAND(h XOR (h SHR 13), POWER(2, 32)-1);`：右移 13 位，按位异或，按位与，清除高位。

- `h := BITAND(h * 3226489909, POWER(2, 32)-1);`：乘以常量，按位与，清除高位。

- `h := BITAND(h XOR (h SHR 16), POWER(2, 32)-1);`：右移 16 位，按位异或，按位与，清除高位。

- `RETURN h;`：返回最终计算出的哈希值。

该函数的作用是计算输入字符串的 MurmurHash3 哈希值，并返回一个 32 位无符号整数。