Blaize11's blog

Maximum and Minimum XOR of a Given Number
By Blaize11, history, 4 years ago, In English

In case you are asked to find out the Number which gives minimum and maximum upon XORing with a given number. The concept is simple.

  1. The minimum XOR result is 0, so the number which produces minimum result upon XOR with a given Number is the Number itself.
  2. The number which produces the maximum XOR is the given number with all its bits flipped.

Bit Flipping LOgic: 1. Find The number of bit. 2. For each of the bits, transverse once and flip the bits.

The C++ code for flipping is:

int flip(int num) { int x=log2(num)+1; // Finding the number of bits for(int i=0; i<x; i++) num=num^(1<<i); // Flipping Each bits of the given number by XORing with the present bit

return num; }

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Lets call $$$X$$$ the number we want to maximize after XORing with another number. The number which produces the maximum XOR is $$$X\oplus{((2^{\infty}-1)\oplus{X})}$$$

Edit: Infinity might have change some properties of the thing so just assume it is a huge number.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    How do you write $$$ 2^{\infty} $$$? What does it mean? Do you define it as the limit of the sequence $$$ 2^x $$$? How do you prove that it converges, and hence you can write the symbol $$$ 2^{\infty} $$$? Or you just use it without care?

    I don't want to be toxic or anything, I just feel like, OP is just a newbie, and is learning new things, and you're certainly not encouraging him, nor do I expect you to. But don't do the opposite. Often on, you want to share your insights to understand stuff better and interact with others to hear their opinion.

    UPD: I might have read your original message in an unintended tone, nvm me.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u please explain what u meant with an example??

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Example number: 1

      You can XOR it with for example 9998 and the result will be 9999.

      You can XOR it with 99998 and it will be 99999

      etc...

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      What your program does is, consider the number which give largest XOR with your number A, with same number of bits as A. If you can have arbitrarily many bits, then after the lower bits of A, you can use 1 in all places in the other number and that will give you a higher XOR

      → Reply