• + 0 comments

    My O(1) Solution

    #include <stdio.h>
    
    int main(void) {
        // a+b = xor(a,b) iff a&b == 0
        long n, res;
        scanf("%li", &n);
        if (!n) {
            puts("1");
        } else if ((n & (n-1)) == 0) {
            printf("%li\n", n);
        } else {
            __asm__ volatile ("popcnt %%rcx, %%rax" :: "c"(n));
            __asm__ volatile ("bsr %rcx, %rcx\n"
                              "inc %rcx\n"
                              "subq %rax, %rcx\n"
                              "movq $1, %r8\n"
                              "shlq %cl, %r8\n");
            __asm__ volatile ("movq %%r8, %0" : "=r"(res));
            printf("%li\n", res);
        }
        return 0;
    }