Двоичные сдвиги и XOR

 
0
 
Алгоритмы
ava
cybear | 03.12.2004, 01:32
(с) 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: Сам решил эту задачу ограниченно - только для В у которых есть решение первого порядка. Сорри если в тексте есть ошибки - скан хреновый.
Ответы (2)
ava
ovr2000 | 04.12.2004, 12:52 #
Элементарно, Ватсон (писал больше чем думал)

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
ava
podval | 04.12.2004, 19:21 #
ovr2000
А словами можно объяснить суть алгоритма?
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
  podval   cybear   ovr2000
advanced
Отправить