Datalab

bitXor(x, y)

Question

要求只能使用 ~ 和 & 实现异或。

Solution

~(a & b) & ~(~a & ~b)

validator:

for(int i = 0; i < 4; i++) {
    int a = i & 1, b = (i >> 1) & 1;
    cout << a << " " << b << " " << ((~(a & b)) & (~((~a) & (~b)))) << endl;
}

这道题做法不唯一，讲道理我都不知道我怎么想出上面的式子的，抄一个别人的答案：

异或定义为 (~a & b) | (a & ~b)

并且有 a | b = ~(~a & ~ b)

得

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

tmin()

Question

Smallest two’s complement integer

Solution

int tmin() {
    return 1 << 31;
}

isTmax(x)

True only if x is largest two’s comp. integer

不能使用 << >>

Solution

bool isTmax(int x) { return (x + 1) & 0x80000000; }

allOddBits(x)

True only if all odd-numbered bits in x set to 1.

错误答案：

bool allOddBits(unsigned int x) {
    return !((x & (x >> 2)) ^ 0x15555555u);
}

会被很多数叉掉，比如 3722304885。

还没想清楚为啥...

Question