(с) EIO 2004/2004

Двоичный СДВИГ
Время работы:1 секунда


Двоичным (битовым) сдвигом данного двоичного числа на один бит влево называют число, которое получается если дописать к изначальному числу справа бит о.
Операция "исключающее или" (которую также называют XOR) является логичеслой операцией на двух логических величинах, результат которой "верно", если ровно один из операндов равен "верно", и "неверно" во всех остальных случаях.
При "сложении" двоичных чисел операцией XOR, их биты рассматривают как логические величины (1 = "верно", О = "неверно") и каждый бит результата считается как XOR соответствующих битов аргументов (младший бит результата - это XOR младших битов аргументов, второй бит результата - XOR вторых битов аргументов, и.т.д.). Например, 0101 XOR 1100 считается следующим образом: младший (самый правый) бит результата равен 1 XOR 0= 1; следующий бит равен 0 XOR 0 = 0; далее 1 XOR 1 = 0; и наконец 0 XOR 1 = 1. В итоге получаем 0101 XOR 1100 = 1001. Так как XOR-сумма двух битов всегда один бит, переводов в следующий разряд не бывает.
Пусть дано n-битное число А. Рассмотрим его двоичные сдвиги s0, s1, ..., sn-1, где s0 означает само число А, и для каждого i > 0, si - это сдвиг числа si-1 на один бит влево.



Далее рассмотрим XOR-суммы чисел si: X0 = s0, И для каждого i > о, Xi = Xi-1 XOR si. К примеру, если А = 1110, то
X0= 1110,
Х1 = 1110 XOR 11100 = 10010,
Х2 = 10010 XOR 111000 = 101010,
Х3 = 101010 XOR 1110000 = 1011010.


Написать программу, которая по заданному В = Хn-1 восстанавливает изначальное число А.




PS: Сам решил эту задачу ограниченно - только для В у которых есть решение первого порядка. Сорри если в тексте есть ошибки - скан хреновый.

Элементарно, Ватсон (писал больше чем думал)

Код

Private Sub Text1_GotFocus()    Dim str As String    Dim res As String    Dim bit As Integer    Dim i, j, k As Integer        str = strChis.Text 'Исходный к-й член    k = CInt(strN.Text) 'Число к- номер члена    If k >= Len(str) Then        strN_Validate True        Exit Sub    End If    res = Right(str, 1)    For j = 1 To Len(strChis.Text) - k - 1        str = Left(str, Len(str) - 1)        bit = CInt(Right(str, 1))        For i = 1 To IIf(j < k, j, k)            bit = bit Xor CInt(Mid(res, i, 1))        Next        res = IIf(bit, "1", "0") & res    Next    Text1.Text = res End Sub

Это сообщение отредактировал(а) ovr2000 - 4.12.2004, 12:53

ovr2000
А словами можно объяснить суть алгоритма?