We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Bit Manipulation
  4. Sum vs XOR
  5. Discussions

Sum vs XOR

Sort by

recency

|

249 Discussions

|

  • quote_unquote
     + 0 comments
    /*
 * Complete the 'sumXor' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts LONG_INTEGER n as parameter.
 */

long sumXor(long n) {
    long count = 0;
    auto s = bitset<64>(n).to_string();
    auto t = s.find_first_of("1");
    for (size_t i = t+1; i < 64; ++i) {
        if (s[i] == '0') { count++; }
    }    
    // cout << count << endl;
    return 1L << count;
}

  • skbenz
     + 0 comments

    sum is essentially xor except, there's the possibility of a carry with addition: 1 ^ 1 == 0, while 1 + 1 = 10. That's why you want to count the number of zeroes in the input. Once you have that, you need all the permutations of toggling those zeroes, which is 2 ** n_zeroes, or 1 << n_zeroes.

    If we choose 100, which is b'110 0100, there are four zeroes, so there are 16 ways to toggle the zeroes -> 0, 1, 10, 11, 1000, 1001, 1010, 1011, 10000, 10001, 10010, 10011, 11000, 11001, 11010, 11011.

  • patrickgao2020
     + 1 comment

    Here is my Python solution! A really clever trick is to realize that the amount is just 2 raised to the amount of 0s in the binary representation of the number.

    def sumXor(n):
    if n == 0:
        return 1
    return 2 ** (bin(n).count("0") - 1)

  • alban_tyrex
     + 0 comments

    Here is my C++ solution, you can watch the explanation here : https://youtu.be/yj0yNv6BZa8

    long sumXor(long n) {
    long result = 1;
    while(n) {
        result *= (n % 2) ? 1 : 2;
        n /= 2;
    }
    return result;
}

  • ze_hkrk
     + 0 comments

    C solution

    long sumXor (long n) {
    long result = 0;
    while(n) {
        if(!(n & 0x1)) {
            result++;
        }
        n = n>>0x1;
    }
    return 0x1ULL << (result);
}