Есть следующие уравнение A & X = C A,C - константы (WORD) X - неизвестное (область определения X - WORD) Чему равно X ? У меня дальше A & X = X & A мыслей нет
диапазону чисел X = (ANY & !A) | C, где ANY любое число со значащими разрядами на месте нулевых разрядов А.
Здесь необходимо смотреть конкретные числа, исходя из аксиом A & 1 = A и A & 0 = 0 т.е. если A=1010 и С=0010, то можно сказать, что X=0?1? где ? может быть как 0 так и 1 Более конкретно, смотрим для i-разряда числа X Там где Ai=1 и Ci=1 Xi=1, там где Ai=1 и Ci=0 Xi=0, там где Ai=0 и Ci=0 Xi=неопределен.
AND - операция побитовая, поэтому можем рассматривать каждый бит отдельно. Т.е. примем A, X, C равными 0 или 1. Тогда A & X = C будет эквивалентно уравнению A*X = C. Отсюда три случая: 1) A==0 и C==0 => X любое 2) A==0 и C==1 => решения нет 3) остальное => X=C/A, что равнозначно X = C & A
Stiver Если теперь перейти к общему случаю (n битов), получаем. Пусть A = (a1, a2, ..., an) C = (c1, c2, ..., cn) Сначала проверяем, что во всех битах не будет ai = 0 и c1 = 1 (т.е. вектор C <= A, что вполне естественно, так как C есть подмножество A). Решения будут формироваться след. образом: в тех позициях, где ai = 1, xi = ci; там же, где ai = 0 и c1 = 0 значение xi будет любое. Число решений будет равно 2^(n - вес вектора A). Вроде так, если не напутал. Пример A = (1010) C = (1000) Решения (1*0*) = {(1000), (1001), (1100), (1101)}.
A = 3 X =5 C=1 A & X = 1 - это C C & A = 1 - это не X Это частное решение, нужно полное решение в которое гарантировано входит мой X
DenKor пусть A = 3 X =5 C=1 исходный пример: 0011 & 0001=0001 0011 & 0101=0001 0011 & 1001=0001 0011 & 1101=0001 восстанавливаем число Х: 0011 ? 0001=XX01 not(A xor C)=1101 - нули, там, где у X нулевые разряды C=0001 - единицы, там, где у числа X единичные разряды 1111 - С - (A xor C)=1100 - единицы, там, где у числа X неопределенные разряды Для того, что бы гарантированно найти Х -- требовалось A xor X = С, тогда A xor C = X
Stiver А вот интересно, как решить уравнение A ^ X = B (^ - пересечение множеств) для двух произвольных множеств A и B?
crypto Хм, вроде бы примерно так же: 1) если B не \subset A => нет решения 2) иначе: X \subset (B AND NOT(A)) Upd.: напутал конечно, должно быть X = B AND subset(NOT(A)))
Stiver Кажись вместо AND должно быть OR (объединение), а то ведь поскольку B - подмножество A, то пересечение B и дополнения A будет пустым. Т.е. решением будет объединение B с любым подмножеством из дополнения A?
crypto Совершенно верно, я имел в виду объединение множеств, только неудачно записал. Надо было + поставить, не догадался. Или целиком в LaTeX'e набирать.
