Notali.haidar's blog

Xor base

By Notali.haidar, history, 6 years ago, In English

-** Hello** , i have a problem,i want to share with you. given n<=10^8,how many bases we have to generate all numbers between 0 and n using only xor operation between element of the base ex: - n=15;the bases can be{1,2,4,8} using these 4 integer i can generate all number between 0 and 15. for n=3 bases could be {1,2} 1=1 2=2 1^2=3 1^1=0 so how many such set we have ps: base=smallest set of numbers that generate all numbers between 0 and N

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

This is an easy problem. The answer is always equal to the smallest integer x such that 2x > n.
1. If we prepare base (20, 21, 22, ..., 2x - 1), we can easily prove that we can generate number between 0 to 2x - 1.
2. If we prepare y integers, obviously there are at most 2y generatable numbers. So, y should be stricly larger than n.
For 1. and 2., we proved that the answer is always equal to the smallest integer x such that 2x > n. Thus we can calculate in O(logn).

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

    i want how many way i can get such set not how many elememt in this set

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +9 Vote: I do not like it

      My idea is as follows (untested, so could be wrong, I welcome corrections):

      From the answer of square1001 we already know that the smallest size for a base is x, where it is the smallest such that 2x > n.

      Now suppose we construct the base by adding numbers to it one by one and consider the set of numbers we can make from the base at any time. It can be shown that each number we add to the base is either useful and we can now form twice as many numbers as before adding it, or useless and we can not form any new numbers than we could before adding it.

      Another observation is that a number k ≥ 2x will never be in the base. I am not going to prove that, but you can see it makes sense intuitively, because such number would have bits that are not present in the numbers from 0 to n, which means it can only then be combined if another such number is XOR-ed with it to remove those bits, yielding pointless increase in base size.

      Let's now go back to useless and useful numbers again. If we have some base and we are adding a new number, then it is useful if and only if it cannot be formed by XOR-ing numbers that are already in the base.

      We can combine the observations to establish the following, regarding the building of the base:

      Suppose we have a base {A1, A2, ..., Am} and we want to add a number Am + 1 to it. Since we want a base of minimum length, clearly the new number must be useful and Am + 1 < 2x must hold. Since all numbers added in the base were useful themselves, then the current base can form exactly 2m different numbers, and clearly all of them in the interval [0, 2x). We can thus conclude that there are 2x - 2m different ways to choose an useful value for Am + 1.

      Since we are building this set starting from 0 elements up to x elements, then the total ways to build the base set of size x is .

      If you want all unordered sets (since this gives ordered sets), then you can simply divide by x!, since any minimal base clearly has only distinct numbers.

      Thus unordered sets are given by:

      For example, take x=2 (i.e. n=2 or n=3). The formula gives for unordered sets the value 3. Indeed the three sets are:

      {1, 2}, {1, 3}, {2, 3}

      Once again, this is just how I think it should be, haven't written any code to confirm this, perhaps a brute-force that gives the values for like x ≤ 4 would at least somewhat confirm if I'm right.

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

        yess you are 100% correct i do the same thing,and i only use brute force sol for(n<=15) and it is coorect

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

          Awesome. In that case feel free to ask more about details of the derivation, in case you need any.

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

square1001 do you understand what i mean sorry my english is newbie

→ Reply