Find XOR of all numbers in a given range

by

This is a pretty clever solution — it exploits the fact that there is a pattern of results in the running XORs. The f() function calculates the XOR total run from [0, a]. Take a look at this table for 4-bit numbers:

0000 <- 0  [a]
0001 <- 1  [1]
0010 <- 3  [a+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [a+1]
0111 <- 0  [0]
1000 <- 8  [a]
1001 <- 1  [1]
1010 <- 11 [a+1]
1011 <- 0  [0]
1100 <- 12 [a]
1101 <- 1  [1]
1110 <- 15 [a+1]
1111 <- 0  [0]

Where the first column is the binary representation and then the decimal result and its relation to its index (a) into the XOR list. This happens because all the upper bits cancel and the lowest two bits cycle every 4. So, that’s how to arrive at that little lookup table.

Now, consider for a general range of [a,b]. We can use f() to find the XOR for [0,a-1] and [0,b]. Since any value XOR’d with itself is zero, the f(a-1) just cancels out all the values in the XOR run less than a, leaving you with the XOR of the range [a,b].

More Related Contents:

  1. Algorithm to find Largest prime factor of a number
  2. Write a function that returns the longest palindrome in a given string
  3. Cycles in an Undirected Graph
  4. Computing set intersection in linear time?
  5. Efficiently find binary strings with low Hamming distance in large set
  6. Roulette wheel selection algorithm [duplicate]
  7. “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
  8. Calculating mid in binary search
  9. Geo Fencing – point inside/outside polygon
  10. Find the missing and duplicate elements in an array in linear time and constant space
  11. Finding closest neighbour using optimized Levenshtein Algorithm
  12. Best Compression algorithm for a sequence of integers
  13. Smoothing data from a sensor
  14. A simple explanation of Naive Bayes Classification [closed]
  15. Basic Recursion, Check Balanced Parenthesis
  16. Euler project #18 approach
  17. Fastest available algorithm for distance transform
  18. What algorithm for a tic-tac-toe game can I use to determine the “best move” for the AI?
  19. Generating integers in ascending order using a set of prime numbers
  20. Big O when adding together different routines
  21. Finding height in Binary Search Tree
  22. How to understand the dynamic programming solution in linear partitioning?
  23. Clustering Algorithm for Mapping Application
  24. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  25. Round to the nearest power of two
  26. Draw equidistant points on a spiral
  27. Comparison-based ranking algorithm
  28. Finding connected components of adjacency matrix graph
  29. Stable separation for two classes of elements in an array
  30. Cache Invalidation — Is there a General Solution?

Leave a Comment