simplification of boolean summation

Discussion in 'Programmer's Corner' started by TomM, Jul 9, 2013.

  1. TomM

    Thread Starter New Member

    Jul 9, 2013
    2
    0
    Hi,

    I have a summation of xors - a (0 to n), b (0 to m) -> sum(a^b).
    ie
    for a in range(0, n):
    for b in range(0, m):
    total+= a^b

    if it were multiplication i could just do
    (n+1)n/2 * (m+1)m/2

    is there a similar simplification i can use for the boolean logic?
     
  2. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,795
    This makes pretty much zero sense.

    How about presenting a simple example, say with n=4, so that we can figure out what you mean?
     
  3. TomM

    Thread Starter New Member

    Jul 9, 2013
    2
    0
    Hi,

    sure

    m = 4
    n = 2
    for a in range(0, m):
    for b in range(0, n):
    total += a^b

    a,b
    0,0 = 0
    0,1 = 1
    0,2 = 2
    1,0 = 1
    1,1 = 0
    1,2 = 3
    2,0 = 2
    2,1 = 3
    2,2 = 0
    3,0 = 3
    3,1 = 2
    3,2 = 1
    4,0 = 4
    4,1 = 5
    4,2 = 6

    total = 34

    if the operator were * instead of xor
    a,b
    0,0 = 0
    0,1 = 0
    0,2 = 0
    1,0 = 0
    1,1 = 1
    1,2 = 2
    2,0 = 0
    2,1 = 2
    2,2 = 4
    3,0 = 0
    3,1 = 3
    3,2 = 6
    4,0 = 0
    4,1 = 4
    4,2 = 8
    total = 30
    2(2+1)/2 = 3
    4(4+1)/2 = 10
    = 3*10 = 30
    thus for the multiplication i go from (n+1)(m+1) multiplications and (m+1)(n+1) additions, to 3 multiplications, 2 additions, and 2 divisions. Ie from O(mn) to O(1). I should be able to get a similar reduction for the sum of xors.
     
  4. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,795
    Okay, I see what you are doing and it is what I figured you were probably getting at.

    Since the XOR is a linear operation, my guess is that you won't find something simple via algebraic manipulation. You will probably need to look for patterns and reductions.

    For instance, if you have m>n, is there anything you can learn from breaking it up into the sum of [0:n]x[0:n] and the sum of [n+1:m]x[0:n]

    You might also look at counting how many times each bit position survives the XOR.
     
Loading...