Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Двоичные сдвиги и XOR

Автор: cybear 3.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: Сам решил эту задачу ограниченно - только для В у которых есть решение первого порядка. Сорри если в тексте есть ошибки - скан хреновый.

Автор: ovr2000 4.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

Автор: podval 4.12.2004, 19:21

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