XORMUL - Editorial

Hey is writing “x |= (1<<i)” same as “x += (1<<i)” , if it is so then how ?
if let say ith bit is 0 then answer will be same in both cases but if ith bit is 1 then it changes. please tell.

Thanks for correcting!

1 Like

heres my greedy approach:
Capture

You can always think in terms of binary representation…Check for yourself…Doing OR or simply adding won’t make any difference if not both of bits are same. In general OR of two numbers and adding will only be different when both bits are set…

1+0 == 1
1|0 == 1
0+1 == 1
0|1 == 1
0+0 == 0
0|0 == 0
But,…
1+1 == 2 i.e. 10
1|1 == 1 i.e. 01

But in this question, num always is power of 2, like 1000…and we are adding 1 bit to 0 bit, so it’s kind of similar to doing OR.

1 Like

That actually sums up everything! Thank you :slight_smile:

A little bit twiddling:

#include <stdio.h>
int main() {
    int n, a, b, r;
    for(scanf("%*d"); ~scanf("%d%d%d", &n, &a, &b);) {
        b ^= a;
        r = b ? ~(a | b) | a & b ^ 1 << 31 - __builtin_clz(b) : ~a;
        printf("%d\n", r & ((1 << n) - 1));
    }
    return 0;
}

Thanks @djaycoding for sharing this solution I really can’t understand author’s solution.

1 Like