Как работает этот генератор перестановок?

Question

Мне дали совет, что следующий код будет работать, и он работает, однако я использую его в небольшом исследовательском проекте, и мне нужно полностью понять, в чем именно заключается его принцип.

for i:=0 to (PNum-1) do begin
for j:=0 to (SMax-1) do begin
write(f, ((i shr j) and 1));
end;
writeln(f);
end;

По сути, он генерирует все вариации PNum длинной строки символа SMax, содержащей 0 и 1. Мой вопрос заключается в том, что делает ((i shr j) and 1) (shr - сдвиг вправо в Паскале)?

Заранее спасибо.

Answer 1

Выражение

((i shr j) and 1)

извлекает j -й бит из двоичного представления `i´ (считая биты с нуля справа).

Пример:

i = 23; j = 3;

bin[23] = 10111    
bin[23 shr 3] = 10111 shr 3 = 10
bin[23 shr 3] and 1 = 10 and 1 = 0

Примечание: алгоритм строит все комбинации из [0,1], если PNum = 2^SMax, а не все перестановки .