_Muhammad's blog

By _Muhammad, history, 6 years ago, In English

After applying Gaussian algorithm on a array how could I restore those numbers of which XOR is maximum?

Let a[3] = {11, 5, 9} If I apply Gaussian algorithm we will find maximum xor is 14.And used numbers are 11, 5.How to restore this 11, 5?

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

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

if you have additional time (where c is the max value) it is easy to restore. Here is a slow implementation, which can be improved to if you replace the bitset and just store by wich indices the value is composed (there are always atmost bits set).

bitset<n> calc(const vector<ll>& in) {
    vector<ll> val = in;
    bitset<n> res;
    vector<bitset<n>> set(in.size());
    for (ll i = 0; i < n; i++) set[i][i] = true;
    ll c = 0;
    while (true) {
        ll m = 0;
        for (ll i = 0; i < n; i++) {
            if (val[m] < val[i]) m = i;
        }
        if (val[m] == 0) return res;
        if ((c ^ val[m]) > c) {
            c ^= val[m];
            res ^= set[m];
        }
        for (ll i = 0; i < n; i++) {
            if (i != m && (val[i] ^ val[m]) < val[i]) {
                val[i] ^= val[m];
                set[i] ^= set[m];
            }
        }
        val[m] = 0;
        set[m].reset();
    }
}
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I did a python 2 implementation to show one way of doing it, in , where m is the number of linear independent binary vectors in A. Note that so it runs really quick, also note that nothing in my implementation is python specific I just really like how pseudo code like python is. The essential stuff lies in the two functions, the rest just shows how to use the functions.

A = [11, 5, 9]

def linear_independent_basis(A):
    basis_indices = []
    while any(A):
        i = max(range(len(A)),key = lambda i: A[i])
        basis_indices.append(i)
        Amax = A[i]
        A = [min(a^Amax,a) for a in A] 
    return basis_indices

def orthogonalize(B):
    m = len(B)
    Bprime = B[:]
    # store bitmasks to remember how to recreate Bprime from B
    bitmasks = [2**i for i in range(m)]
    for i in range(m):
        for j in range(m):
            if i!=j and Bprime[i]^Bprime[j]<Bprime[j]:
                Bprime[j]^=Bprime[i]
                bitmasks[j]^=bitmasks[i]
    return Bprime, bitmasks
    
# Find a linear independent basis B
basis_indices = linear_independent_basis(A)
B = [A[i] for i in basis_indices]
m = len(B)
print 'Linear independent basis:', [bin(b) for b in B]

# "Orthogonalize" the basis
Bprime, bitmasks = orthogonalize(B)
print 'Orthogonalized basis:', [bin(b) for b in Bprime]

# With the basis "orthogonalized" you get the maximum xor by just xoring everything
maxval = 0
for b in Bprime:
    maxval ^= b
print 'Max xor is', maxval

# The bitmask contains information of how to create maxval from B
maxval_bitmask = 0
for bitmask in bitmasks:
    maxval_bitmask ^= bitmask

# So maxval can also be found using the bitmask
maxval = 0
bit = 1
for i in range(m):
    if bit&maxval_bitmask:
        print 'Using', A[basis_indices[i]]
        maxval ^= A[basis_indices[i]]
    bit *= 2
print 'Max xor is', maxval

The output is

Linear independent basis: ['0b1011', '0b101', '0b1001']
Orthogonalized basis: ['0b1001', '0b101', '0b10']
Max xor is 14
Using 11
Using 5
Max xor is 14
  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I didn't get anything. I have a little knowledge of python. But thanks.You tried to help me.