Way to efficiently calculate XOR(^) checksum based on a list of IDs

Question

When googling information about Python list comprehension I was offered a google foobar challenge, which I've been slowly working on the past few days for fun. The latest challenge:

effectively calls for generating a list of IDs, ignoring an increasing number from each new line until there's one ID left. Then you are supposed to XOR(^) the IDs to produce a checksum. I created a working program that outputs the correct answer, however it's not efficient enough to pass all test cases(passes 6/10) in the time allotted. A length of 50,000 should produce a result in under 20 seconds, but it takes 320.

Could someone steer me in the right direction, but please don't do it for me, I'm having fun pushing myself with this challenge. Perhaps there's a data structure or algorithm I can implement to speed up the computation time?

Logic behind code:

1. First, the starting ID and length are taken in

2. A list of IDs is generated, ignoring an increasing number of IDs from each new line, starting with ignoring 0 from the first line.

3. XORs all of the numbers in the list of IDS using a for loop

4. Answer is returned as an int

---

import timeit
def answer(start,length):
    x = start
    lengthmodified = length
    answerlist = []
    for i in range (0,lengthmodified): #Outter for loop runs an amount of times equal to the variable "length".
        prestringresult = 0
        templist = []
        for y in range (x,x + length): #Fills list with ids for new line
            templist.append(y)
        for d in range (0,lengthmodified): #Ignores an id from each line, increasing by one with each line, and starting with 0 for the first
            answerlist.append(templist[d])
        lengthmodified -= 1
        x += length    
        for n in answerlist: #XORs all of the numbers in the list via a loop and saves to prestringresult
            prestringresult ^= n
        stringresult = str(prestringresult) 
        answerlist = [] #Emptys list
        answerlist.append(int(stringresult)) #Adds the result of XORing all of the numbers in the list to the answer list
    #print(answerlist[0]) #Print statement allows value that's being returned to be checked, just uncomment it
    return (answerlist[0]) #Returns Answer



#start = timeit.default_timer()
answer(17,4)
#stop = timeit.default_timer()
#print (stop - start) 

Answer 1

You'll likely need a different approach, not just minor improvements like John's. I just wrote a solution that can do answer(0, 50000) in about 2 seconds on my PC. I still do it row by row, but instead of xoring all numbers in the row's range, I do it bit by bit. How many numbers in the row have the 1-bit set?^[*] An odd number of numbers? Then I flip the 1-bit of my answer. And then the same with for the 2-bit, the 4-bit, the 8-bit, etc, up to the 2³⁰-bit. So for each row, it's just 31 little calculations (instead of actually xoring tens of thousands of numbers).

[*] Can be computed quickly in constant time just from start/stop of the range.

Edit: Since you asked for another hint, here's how to compute how often the 1-bit is set in some range(a, b). Compute how often it's set in the range(0, a) and subtract that from how often it's set in the range(0, b). It's easier if the range starts at zero. How often is the 1-bit set in some range(0, c)? Easy: c//2 times. So how often is the 1-bit set in some range(a, b)? Simply b//2 - a//2 times. The higher bits are similar, just a little more complicated.

Edit 2: Oh wait, I just remembered... there's an easy way to compute the xor of all numbers in some range(a, b). Again split the work into doing range(0, a) and range(0, b). The xor of all numbers in some range(0, c) is easy because there's a nice pattern (you'll see it if you do it for all c from 0 to let's say 30). Using this, I now solve answer(0, 50000) in about 0.04 seconds.