使用XOR运算符计算校验和

Question

作为Google挑战的一部分，我试图回答一个相当困难的问题，这个问题涉及到使用XOR操作符来计算校验和。当我的解决方案工作时，我的算法在O(n)时间内工作，而所需的解决方案似乎需要更快。

您可以看到挑战这里的文本。

虽然我知道该线程中提供的帮助是有效的，但解决方案是用Python提供的，而且我正在使用Java。有人能解释为什么我的解决方案效率低下，以及如何改进它吗？我是一个自学成才的程序员，所以对我来说，公司的一些奥秘是个谜。

static int answer(int start, int length) {
    int checksum = 0;
    int dividerPos = length;
    int count = start;
    int idx = 0;

    while(true) {
        if(dividerPos == 0)
            return checksum;
        else if (idx == dividerPos) {
            count += (length - dividerPos);
            --dividerPos;
            idx = 0;

            continue;
        }

        checksum ^= count;

        ++idx;
        ++count;
    }
}

Answer 1

• 在有些情况下，无限循环while (true)是必要的，这不是其中之一。代码意味着当dividerPost达到零时，循环就会中断。显式地说:虽然(dividerPos > 0) { if (idx == dividerPos) { count += (长度- dividerPos)；--dividerPos；idx = 0；继续；}校验和^=计数；++idx；++count；}返回校验和；
• 现在很容易看出，循环的主体是另一个伪装的循环。同样，要显式: while (dividerPos > 0) { for (idx = 0；idx < dividerPos；idx++，count++) {校验和^=计数；} count += (长度- dividerPos)；-dividerPos；}
• 现在可以清楚地看到代码正在做什么，以及它在做什么效率低下的事情。一个立即确定的瓶颈是一个内环。它所做的是计算一个数字范围的xor ( xor of a range查询的第一个成功例子是这讨论)。研究它，看看它是如何适用于这里。这本身就会给你的代码一个提升。然后尝试优化外部循环。

PS:重要的是要理解语言并不重要。

PPS:对不起，如果我听起来很严厉，但是当我说学习的时候，我指的是学习。别脱脂。明白它是怎么工作的。证明它是正确的。

公私伙伴关系:你所链接的页面中的两个答案都忽略了重点。