Что делает этот цикл?

Question

Что делает следующий цикл?

k = 0
while(b!=0): 
   a = a^b 
   b = (a & b) << 1 
   k = k + 1 

где a, b и k целые числа.

Первоначально a = 2 ⁷⁷⁹ и b = 2 ⁶² , тогда что будет значением k после завершения цикла?

Я был бы рад, если бы вы, люди, попытались решить проблему вручную, а не программно.

EDIT : удаление тегов c и c ++. Как я могу решить проблему вручную?

Answer 1

После выполнения этого чанка:

a = a^b ;
b = (a & b) << 1;

b примет целочисленное представление любых битов, которые были установлены в b и не установлены в a.Предполагая, что входные числа будут иметь вид 2 ^x , a станет a + b, а b само умножится на 2 (из-за смещения).Это означает, что цикл завершится, когда старшие биты a и b будут одинаковыми (в этом примере это будет 780-й бит).Поскольку b начинается с 63-го бита, в конечном итоге будет 718 итераций: 780 - 63 + 1 (последняя итерация) = 718.

Это можно увидеть, когда вы пройдете через это с помощью a= 2 ¹ и b = 2 ⁰ :

a = 10
b = 01
k = 0

a = 11
b = 10
k = 1

a = 01 (a + b no longer holds here, but it is irrelevant as this is the termination case)
b = 00
k = 2

Answer 2

Что делает следующий цикл?

Он вычисляет [мощность a] - [мощность b] + 1

Есливы смотрите на битовые паттерны, это становится совершенно ясно.Для начальных значений a = 2 ¹⁰ и b = 2 ⁵ это выглядит так:

k =  0, a = 10000000000, b =       100000
k =  1, a = 10000100000, b =      1000000
k =  2, a = 10001100000, b =     10000000
k =  3, a = 10011100000, b =    100000000
k =  4, a = 10111100000, b =   1000000000
k =  5, a = 11111100000, b =  10000000000

Здесь - идеон.com demo.

Для значений, которые вы упоминаете в своем посте, я получаю k = 718.

Answer 3

Это не совсем синтаксис Си .. Если мы посмотрим, что код последовательный, я согласен с @Paul.Но, учитывая, что

a + b == (a^b) + ((a&b) << 1)

, где a^b - это сумма без применения переноса из каждого бита, а (a&b)<<1 - переноса из каждого бита, можно сказать, что он выполняет суммирование, IFF C-код будет

int k = 0;
while(b){ 
   int old_a = a;
   a = a^b;
   b = (old_a & b) << 1; // note that the need the original value of a here
   k++;  // number of recursion levels for carry
};

Разница в коде может быть из-за "параллельного" способа выполнения в исходном коде (или языке).

Answer 4

Поскольку вы упомянули, что qnd b является целым числом, я думаю, что значение 2 ⁷⁷⁹ слишком велико для целочисленной переменной, чтобы вместить его, то же самое для переменной b 2 ⁶² также. Я думаю, что оба будут иметь минимальное значение, поэтому после выполнения a = a ^ b; b = (a & b) << 1; В этих утверждениях значение a и be будет равно 0. А значение k будет равно 1. Поскольку b равно 0, условие цикла while будет ложным, и оно выйдет из цикла. </p>

РЕДАКТИРОВАТЬ: Ответ применим для таких языков программирования, как C / C ++ или C #

Answer 5

Похоже, что цикл выполняет серию побитовых операций, увеличивая k на 1 на каждой итерации.

Здесь есть приличное руководство по побитовым операторам .

Надеюсь, это поможет.

Answer 6

На языке, который поддерживает такие большие числа, ответ 718, и вопрос в любом случае не интересен.