Сумма специальной функции в диапазоне

Question

Я хочу вычислить сумму функции, определенной над [L, R].

Функция сначала вычисляет xor каждой подстроки числа, а затем добавляет различные значения, вычисленные и возвращающие.

Eg: F(312) 
    3 = 3 
    3^1 = 2 
    3^1^2 = 0 
    1 = 1 
    1^2 = 3 
    2 = 2 
    Sum of distinct values = 3+2+1 = 6 = F(312) 

Как я могу рассчитать это быстро? L, R может находиться в диапазоне от 1 до 1000000000.

Например: если я даю L = 5 и R = 15, тогда функция должна вычислять F (5) + F (6) + F (7) ... + F (15)

Answer 1

Одно из возможных решений в JavaScript может выглядеть так: функция

<script type="text/javascript"> 

function sumXorSubStr(numStr) 
{ 
    numStr = parseInt(numStr).toString(); 

    var 
    results = {}, 
    lastPos = numStr.length -1 
    ; 

    for(var start=0 ; start <= lastPos ; start++) 
    for(var op = 0, i = start ; i <= lastPos ; i++) 
     results[ op ^= numStr[i] ] = 1; 

    var sum = 0; 
    for(var i in results) 
    sum += parseInt(i); 
    return sum; 
} 

alert(sumXorSubStr(312)); 

</script> 

обертку в цикле из/является оптимальным способом. Побольше производительности можно достичь, объединив его в одну функцию.

function sumRangeXorSubStr(from, to) 
{ 
    var result = 0; 

    for(var n=from; n<=to; n++) 
    result += sumXorSubStr(n); 

    return result; 
} 

Я некоторое представление о более производительном способе, не уверен, если я достану ...