We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Bit Manipulation
  4. Xor-sequence
  5. Discussions

Xor-sequence

  • tuan_lq121100
     + 0 comments

    There is a pattern of 4 consecutive elements in the array A, for example: A[0] -> A[3], and so on. The first number of the sequence = it's index, the 2nd number is 1, the third = index of the fourth and the fourth = 0. And, when you xor all 4 together, you always get 2. When you xor 2 sequences, you get 0, so it doesn't affect the remaining xor. Base on that, you can just find the effective xor, which are from left to the next start sequence index and from right back to the index after the last 8-element sequence.

    function getValue (idx) {
    let dp = 0n;
    let remain = idx % 4n;
    if(remain === 0n) dp = idx;
    if(remain === 1n) dp = 1n;
    if(remain === 2n) dp = idx+1n;
    if(remain === 3n) dp = 0n;   
    return dp;
}
function xorSequence(l, r) {
    [l, r] = [BigInt(l),BigInt(r)];
    if(l === r) return getValue(l);
    let output = getValue(l);
    let nextSequenceIdx = 4n*((l - l%4n)/4n + 1n);
    let leftoverIdxs  = (r-nextSequenceIdx+1n) % 8n;
    for(let i=l+1n; i<nextSequenceIdx;i++) {
        output = output^getValue(i);
    }
    for(let i=r; i>r-leftoverIdxs;i--) {
        output = output^getValue(i);
    }
    return output;
}