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. The Great XOR
  5. Discussions

The Great XOR

Sort by

recency

|

166 Discussions

|

  • patrickgao2020
     + 0 comments

    Here is my Python solution!

    def theGreatXor(x):
    amount = 0
    greatest = int(math.log(x, 2))
    for num in range(greatest):
        if (2 ** num) ^ x > x:
            amount += 2 ** num
    if (2 ** greatest) ^ x > x:
        amount += x - 2 ** greatest
    return amount

  • jmcparland
     + 0 comments

    Haskell

    module Main where

import Data.Bits (Bits (shiftR, testBit))

solve :: Integer -> Integer
solve x = go x 0 0
  where
    go 0 idx acc = acc
    go n idx acc =
        if testBit n 0
            then go (shiftR n 1) (idx + 1) acc
            else go (shiftR n 1) (idx + 1) (acc + 2 ^ idx)

main :: IO ()
main = getLine >> getContents >>= mapM_ (print . solve . read) . lines

  • johnny_reed
     + 1 comment

    For x > 0, you can just subtract input from an equal number of "on" bits, e.g.

    if x = 1010 perform: 1111 - 1010 and that's the answer.

    I haven't found a really easy way (in C++) of making that 1111 number, though.

  • jvk2117
     + 0 comments

    If you use the easy to code approach where you check every number, you can get the correct answer for small numbers. If you understand bits you'll be able to see that the correct answer is the invert of the original number. EX: 10 (0000 1010) - Answer: 5 (0000 0101) So what you can do is invert the bits until you reach the leftmost bit value on the original. C#:

    public static long theGreatXor(long x)
    {
        long result = 0;
        int i = 0;
        while(x > 1)
        {
            if((x & 1) == 0)
            {
                result ^= (long)1 << i;
            }
            x >>= 1;
            i++;
        }
        
        return result;
    }

  • kb_kevinbinet
     + 0 comments

    def theGreatXor(x): list_val_bin = list(bin(x)) y = (2**(len(list_val_bin)-2))-1 return int(bin(x ^ y), 2)