Решить систему уравнений с побитовыми операциями

@CodeKing · Регистрация: 07.11.2019

Author24 — интернет-сервис помощи студентам

Assembler

1 2	(a11 & x) ^ (a12 & y) = b1 (a21 & x) ^ (a22 & y) = b2

Мне данны a11,a12,a21,a22,b1,b2.Помогите пожалуйста составить уравнение которое позволит найти x и y.Только пожалуйста не кодом а так же уравнением,писать буду на Ассемблере.Заранее благодарю.

Verevkin · 03.03.2020, 16:33

Код

(a21 & x) ^ (a22 & y) = b2,
a21 & x = b2 ^ (a22 & y),
x = (b2 ^ (a22 & y)) & !a21 + 1

Теперь то, что справа, надо подставить в первое уравнение вместо х и выразить y.
Но это неточно.

@Annemesski · 03.03.2020, 16:35

x = b1 & a11
y = b1 & !a11 & a12

Verevkin · 03.03.2020, 16:47

Сообщение от Annemesski

Код

x = b1 & a11
y = b1 & !a11 & a12

a21 и a22 на результат не влияют?

@CodeKing · 03.03.2020, 17:45 **[ТС]**

Annemesski,а что означает ! и как мне получить данное представление?

Verevkin · 03.03.2020, 17:49

Сообщение от CodeKing

а что означает !

инверсия.

@CodeKing · 11.03.2020, 18:30 **[ТС]**

Помогите пожалуйста составить уравнение которое находит x и y.Нам известны a11, a12, a21, a22, b1, b2.Просто уравнением код не нужен.Заранее благодарю.

(a11 & x) ^ (a12 & y) = b1
(a21 & x) ^ (a22 & y) = b2

ФедосеевПавел · 11.03.2020, 19:57

Это же не алгебра.
Беглый поиск по фразе "решение булевых уравнений" приводит к массе любопытных методичек, в том числе и для ЕГЭ.
Как понимаю, никто из нас ЕГЭ не сдавал, поэтому булевы уравнения решать не можем.

Из прочтения сделал вывод, что при произвольных значениях a11,a12,a21,a22,b1,b2 система уравнений решается перебором.
Если эти значения известны заранее, то система уравнений принимает некоторый определённый вид, который можно решать аналитически.

Это моё личное мнение.

Verevkin · 11.03.2020, 20:02

Сообщение от ФедосеевПавел

решение булевых уравнений

А я думал, что это битовые операции с целыми операндами.

ФедосеевПавел · 11.03.2020, 20:11

А есть серьёзная разница?
Пусть весь набор (a11,a12,a21,a22,b1,b2), а так же искомые (x, y) это числа по 32 разряда каждое.
Тогда получаем для каждого номера бита по одной системе уравнений. И для каждой системы отсутствие или несколько решений.
Решая каждую из систем для определённого бита - получаем ответ.

ФедосеевПавел · 11.03.2020, 20:28

Для булевых уравнений и систем уравнений нет простых способов решения, приводящих к аналитическому решению.

Лично моё мнение, что эта система решается перебором четырёх вариантов значений x и y.
При этом, для какого-то конкретного набора параметров (a11,a12,a21,a22,b1,b2) решений может не быть совсем, а может быть до 4 решений (по числу комбинаций x и y).

Возможная оптимизация - сохранение решения для конкретного уже рассмотренного набора (a11,a12,a21,a22,b1,b2) и его повторное использование.

Мне лень, но лично вы можете найти аналитические решения для всех 64 комбинаций бит (a11,a12,a21,a22,b1,b2). А можете их просто перебрать в цикле.

@AlexVRud · 11.03.2020, 21:47

Сообщение от CodeKing

Только пожалуйста не кодом а так же уравнением

Увы. для 64 вариантов систем уравнений имеем:

нет решений: 25 раз
одно решение: 19 раз
два разных решения: 16 раз
три разных решения: 3 раза
верно при любых x и y: 1 раз

Так что пишем на Ассемблере перебор

Добавлено через 2 минуты
(1 & x) ^ (1 & y) = 1
(1 & x) ^ (1 & y) = 1
(x, y) == (1, 0), (0, 1), (1, 1),

@CodeKing · 11.03.2020, 22:03 **[ТС]**

ФедосеевПавел Программа должна вывести два беззнаковых числа чила x и y, удовлетворяющих данной системе. Гарантируется, что такие числа всегда найдутся. Если у системы уравнений несколько решений - выводите любое.

При решении задачи запрещается использовать инструкции условной передачи данных и управления.

При данном условию есть ли какое то уравнение с помощью которого можно найти x и y при любых значениях остальных переменных?Писать буду на SASM.Я просто слаб в битовых операциях.Просто нужно выразить х как y затем подставить его во второе уравнение.Но вот как незнаю.

ФедосеевПавел · 11.03.2020, 22:59

CodeKing, это лабораторка, вся математика к ней - в методичке или лекциях. А так же - в интернете по запросу "решение булевых уравнений".

Аналитического решения для них всё равно - нет. Иначе бы шифры взламывались очень легко.
Т.е. формул x=f1(a11,a12,a21,a22,b1,b2), y=f2(a11,a12,a21,a22,b1,b2) - не существует.

Могу посоветовать табличный метод. Разных битовых комбинаций параметров (a11,a12,a21,a22,b1,b2) всего 64. Значит для каждой комбинации можно просчитать значения x и y, занести их в массивы на 64 элемента. По очередной комбинации (a11,a12,a21,a22,b1,b2) из двух массивов извлекать x и y. Вот и нет условных переходов и присвоений.
Как вы будете распознавать отсутствие решения без условных переходов - не понятно.

Без шуток - что по поводу решения думают сокурсники и преподаватель? Какие варианты?

@AlexVRud · 11.03.2020, 23:47

ФедосеевПавел, Для его задачи существует.

Строим таблицу истинности:

Bash

a11     a12     a21     a22     b1      b2      x       y
0       0       0       0       0       0       0       0
0       0       0       0       1       0       _       _
0       0       0       0       0       1       _       _
0       0       0       0       1       1       _       _
1       0       0       0       0       0       0       0
1       0       0       0       1       0       1       0
1       0       0       0       0       1       _       _
1       0       0       0       1       1       _       _
0       1       0       0       0       0       0       0
0       1       0       0       1       0       0       1
0       1       0       0       0       1       _       _
0       1       0       0       1       1       _       _
1       1       0       0       0       0       0       0
1       1       0       0       1       0       1       0
1       1       0       0       0       1       _       _
1       1       0       0       1       1       _       _
0       0       1       0       0       0       0       0
0       0       1       0       1       0       _       _
0       0       1       0       0       1       1       0
0       0       1       0       1       1       _       _
1       0       1       0       0       0       0       0
1       0       1       0       1       0       _       _
1       0       1       0       0       1       _       _
1       0       1       0       1       1       1       0
0       1       1       0       0       0       0       0
0       1       1       0       1       0       0       1
0       1       1       0       0       1       1       0
0       1       1       0       1       1       1       1
1       1       1       0       0       0       0       0
1       1       1       0       1       0       0       1
1       1       1       0       0       1       _       _
1       1       1       0       1       1       1       0
0       0       0       1       0       0       0       0
0       0       0       1       1       0       _       _
0       0       0       1       0       1       0       1
0       0       0       1       1       1       _       _
1       0       0       1       0       0       0       0
1       0       0       1       1       0       1       0
1       0       0       1       0       1       0       1
1       0       0       1       1       1       1       1
0       1       0       1       0       0       0       0
0       1       0       1       1       0       _       _
0       1       0       1       0       1       _       _
0       1       0       1       1       1       0       1
1       1       0       1       0       0       0       0
1       1       0       1       1       0       1       0
1       1       0       1       0       1       _       _
1       1       0       1       1       1       0       1
0       0       1       1       0       0       0       0
0       0       1       1       1       0       _       _
0       0       1       1       0       1       1       0
0       0       1       1       1       1       _       _
1       0       1       1       0       0       0       0
1       0       1       1       1       0       _       _
1       0       1       1       0       1       0       1
1       0       1       1       1       1       1       0
0       1       1       1       0       0       0       0
0       1       1       1       1       0       _       _
0       1       1       1       0       1       1       0
0       1       1       1       1       1       0       1
1       1       1       1       0       0       0       0
1       1       1       1       1       0       _       _
1       1       1       1       0       1       _       _
1       1       1       1       1       1       1       0

По ней КНФ, и остаётся только найти способ упростить всё это

ФедосеевПавел · 12.03.2020, 00:03

Да - таблица в виде двух массивов x и y. А индекс - составляется из битов (a11,a12,a21,a22,b1,b2).

@AlexVRud · 12.03.2020, 01:59

УПС

Закралась в моей программе не простительная ошибка, так что все предыдущие формулы и таблицы были с ошибочкой.

C++

x = (a11 & ~a12 & ~a21 & ~a22 & b1 & ~b2) |
    (a11 & a12 & ~a21 & ~a22 & b1 & ~b2) |
    (~a11 & ~a12 & a21 & ~a22 & ~b1 & b2) |
    (a11 & ~a12 & a21 & ~a22 & b1 & b2) | (~a11 & a12 & a21 & ~a22 & ~b1 & b2) |
    (~a11 & a12 & a21 & ~a22 & b1 & b2) | (a11 & a12 & a21 & ~a22 & ~b1 & b2) |
    (a11 & a12 & a21 & ~a22 & b1 & b2) | (a11 & ~a12 & ~a21 & a22 & b1 & ~b2) |
    (a11 & ~a12 & ~a21 & a22 & b1 & b2) | (a11 & a12 & ~a21 & a22 & b1 & ~b2) |
    (a11 & a12 & ~a21 & a22 & ~b1 & b2) | (~a11 & ~a12 & a21 & a22 & ~b1 & b2) |
    (a11 & ~a12 & a21 & a22 & b1 & ~b2) | (a11 & ~a12 & a21 & a22 & b1 & b2) |
    (~a11 & a12 & a21 & a22 & b1 & ~b2) | (~a11 & a12 & a21 & a22 & ~b1 & b2) |
    (a11 & a12 & a21 & a22 & b1 & b2);
y = (~a11 & a12 & ~a21 & ~a22 & b1 & ~b2) |
    (~a11 & a12 & a21 & ~a22 & b1 & ~b2) | (~a11 & a12 & a21 & ~a22 & b1 & b2) |
    (a11 & a12 & a21 & ~a22 & b1 & ~b2) | (a11 & a12 & a21 & ~a22 & ~b1 & b2) |
    (~a11 & ~a12 & ~a21 & a22 & ~b1 & b2) |
    (a11 & ~a12 & ~a21 & a22 & ~b1 & b2) | (a11 & ~a12 & ~a21 & a22 & b1 & b2) |
    (~a11 & a12 & ~a21 & a22 & b1 & b2) | (a11 & a12 & ~a21 & a22 & ~b1 & b2) |
    (a11 & a12 & ~a21 & a22 & b1 & b2) | (a11 & ~a12 & a21 & a22 & b1 & ~b2) |
    (a11 & ~a12 & a21 & a22 & ~b1 & b2) | (~a11 & a12 & a21 & a22 & b1 & ~b2) |
    (~a11 & a12 & a21 & a22 & b1 & b2);

Лучше не стало

murderer · 12.03.2020, 06:19

Мне данны a11,a12,a21,a22,b1,b2.

То есть известны конкретные значения?

Добавлено через 38 минут
У меня сошлось только при a11,a12,a21,a22,b1,b2=0. Может где-то накосячил?

Кликните здесь для просмотра всего текста

Delphi

{$APPTYPE CONSOLE}
var
  i:     longword;
  coeff: packed record
         case byte of
         0:(a11,a12,a21,a22,b1,b2: byte);
         1:(z:   int64);
         end;
begin
  for i:=0 to 63 do
    with coeff do
    begin
      //эмуляция pdep
      z:=(i*$0101010101010101) and $8040201008040201;
      a12:=a12 shr 1;
      a21:=a21 shr 2;
      a22:=a22 shr 3;
      b1 :=b1  shr 4;
      b2 :=b2  shr 5;
      //проверка выражения для всех комбинаций x и y
      if (((a11 and 0)xor(a12 and 0)=b1)and((a21 and 0)xor(a22 and 0)=b2))and
         (((a11 and 0)xor(a12 and 1)=b1)and((a21 and 0)xor(a22 and 1)=b2))and
         (((a11 and 1)xor(a12 and 0)=b1)and((a21 and 1)xor(a22 and 0)=b2))and
         (((a11 and 1)xor(a12 and 1)=b1)and((a21 and 1)xor(a22 and 1)=b2))then
      begin
        writeln('(',a11,'&x)^(',a12,'&y)=',b1);
        writeln('(',a21,'&x)^(',a22,'&y)=',b2);
      end;
    end;
    readln;
end.

@~~Holiday13~~ · 12.03.2020, 06:21

если перебирать в пределах самого "длинного" в битах числа

C++

    int a11=1,a12=2,b1=3;
    //cout<<"a11 a12 b1: ";
    //cin>>a11>>a12>>b1;
    int a21=4,a22=5,b2=1;
    //cout<<"a21 a22 b2: ";
    //cin>>a21>>a22>>b2;
    for(int x=0; x<=7; x++)
        for(int y=0; y<=7; y++)
            if((a11 & x ^ a12 & y) == b1)
            if((a21 & x ^ a22 & y) == b2)
                cout<<x<<" "<<y<<endl;//4 решения

murderer · 12.03.2020, 07:31

Да с кодом я тупанул.

Добавлено через 6 минут
Verevkin

a21 & x = b2 ^ (a22 & y),
x = (b2 ^ (a22 & y)) & !a21 + 1

Это ведь всё равно, что утверждать
z&x=y
x=y&!z+1
Подставим произвольные значения x=0, y=0, z=1
1&0=0 - верно
0=0&!1+1=0&0+1=1 - не верно

Добавлено через 23 минуты
Мне кажется,что операции & и + в отличие от ^ и ! необратимы. Следовательно решение возможно только перебором.

То есть операция x&0 необратимо уничтожит информацию, содержащуюся в x. А вот ^ можно обратить (X^Y)^Y=X.

ФедосеевПавел Модератор 8541 / 4393 / 1651 Регистрация: 01.02.2015 Сообщений: 13,649 Записей в блоге: 9
	11.03.2020, 22:59	14
	CodeKing, это лабораторка, вся математика к ней - в методичке или лекциях. А так же - в интернете по запросу "решение булевых уравнений". Аналитического решения для них всё равно - нет. Иначе бы шифры взламывались очень легко. Т.е. формул x=f1(a11,a12,a21,a22,b1,b2), y=f2(a11,a12,a21,a22,b1,b2) - не существует. Могу посоветовать табличный метод. Разных битовых комбинаций параметров (a11,a12,a21,a22,b1,b2) всего 64. Значит для каждой комбинации можно просчитать значения x и y, занести их в массивы на 64 элемента. По очередной комбинации (a11,a12,a21,a22,b1,b2) из двух массивов извлекать x и y. Вот и нет условных переходов и присвоений. Как вы будете распознавать отсутствие решения без условных переходов - не понятно. Без шуток - что по поводу решения думают сокурсники и преподаватель? Какие варианты? 0

Verevkin Злостный нарушитель 9598 / 5191 / 1185 Регистрация: 12.03.2015 Сообщений: 24,512
	03.03.2020, 16:33	2
	Код (a21 & x) ^ (a22 & y) = b2, a21 & x = b2 ^ (a22 & y), x = (b2 ^ (a22 & y)) & !a21 + 1 Теперь то, что справа, надо подставить в первое уравнение вместо х и выразить y. Но это неточно. 1

@Annemesski 2565 / 1277 / 468 Регистрация: 08.11.2016 Сообщений: 3,525
	03.03.2020, 16:35	3
	`x = b1 & a11` `y = b1 & !a11 & a12` 0

Verevkin Злостный нарушитель 9598 / 5191 / 1185 Регистрация: 12.03.2015 Сообщений: 24,512
	03.03.2020, 16:47	4
	Сообщение от Annemesski Код x = b1 & a11 y = b1 & !a11 & a12 a21 и a22 на результат не влияют? 0

@CodeKing 67 / 1 / 0 Регистрация: 07.11.2019 Сообщений: 56
	03.03.2020, 17:45 [ТС]	5
	Annemesski,а что означает ! и как мне получить данное представление? 0

Verevkin Злостный нарушитель 9598 / 5191 / 1185 Регистрация: 12.03.2015 Сообщений: 24,512
	03.03.2020, 17:49	6
	Сообщение от CodeKing а что означает ! инверсия. 1

@CodeKing 67 / 1 / 0 Регистрация: 07.11.2019 Сообщений: 56
	11.03.2020, 18:30 [ТС]	7
	Помогите пожалуйста составить уравнение которое находит x и y.Нам известны a11, a12, a21, a22, b1, b2.Просто уравнением код не нужен.Заранее благодарю. (a11 & x) ^ (a12 & y) = b1 (a21 & x) ^ (a22 & y) = b2 0

ФедосеевПавел Модератор 8541 / 4393 / 1651 Регистрация: 01.02.2015 Сообщений: 13,649 Записей в блоге: 9
	11.03.2020, 19:57	8
	Это же не алгебра. Беглый поиск по фразе "решение булевых уравнений" приводит к массе любопытных методичек, в том числе и для ЕГЭ. Как понимаю, никто из нас ЕГЭ не сдавал, поэтому булевы уравнения решать не можем. Из прочтения сделал вывод, что при произвольных значениях a11,a12,a21,a22,b1,b2 система уравнений решается перебором. Если эти значения известны заранее, то система уравнений принимает некоторый определённый вид, который можно решать аналитически. Это моё личное мнение. 0

Verevkin Злостный нарушитель 9598 / 5191 / 1185 Регистрация: 12.03.2015 Сообщений: 24,512
	11.03.2020, 20:02	9
	Сообщение от ФедосеевПавел решение булевых уравнений А я думал, что это битовые операции с целыми операндами. 0

ФедосеевПавел Модератор 8541 / 4393 / 1651 Регистрация: 01.02.2015 Сообщений: 13,649 Записей в блоге: 9
	11.03.2020, 20:11	10
	А есть серьёзная разница? Пусть весь набор (a11,a12,a21,a22,b1,b2), а так же искомые (x, y) это числа по 32 разряда каждое. Тогда получаем для каждого номера бита по одной системе уравнений. И для каждой системы отсутствие или несколько решений. Решая каждую из систем для определённого бита - получаем ответ. 0

ФедосеевПавел Модератор 8541 / 4393 / 1651 Регистрация: 01.02.2015 Сообщений: 13,649 Записей в блоге: 9
	11.03.2020, 20:28	11
	Для булевых уравнений и систем уравнений нет простых способов решения, приводящих к аналитическому решению. Лично моё мнение, что эта система решается перебором четырёх вариантов значений x и y. При этом, для какого-то конкретного набора параметров (a11,a12,a21,a22,b1,b2) решений может не быть совсем, а может быть до 4 решений (по числу комбинаций x и y). Возможная оптимизация - сохранение решения для конкретного уже рассмотренного набора (a11,a12,a21,a22,b1,b2) и его повторное использование. Мне лень, но лично вы можете найти аналитические решения для всех 64 комбинаций бит (a11,a12,a21,a22,b1,b2). А можете их просто перебрать в цикле. 0

@AlexVRud 693 / 303 / 99 Регистрация: 04.07.2014 Сообщений: 846
	11.03.2020, 21:47	12
	Сообщение было отмечено politoto как решение Решение Сообщение от CodeKing Только пожалуйста не кодом а так же уравнением Увы. для 64 вариантов систем уравнений имеем: нет решений: 25 раз одно решение: 19 раз два разных решения: 16 раз три разных решения: 3 раза верно при любых x и y: 1 раз Так что пишем на Ассемблере перебор Добавлено через 2 минуты (1 & x) ^ (1 & y) = 1 (1 & x) ^ (1 & y) = 1 (x, y) == (1, 0), (0, 1), (1, 1), 2

@CodeKing 67 / 1 / 0 Регистрация: 07.11.2019 Сообщений: 56
	11.03.2020, 22:03 [ТС]	13
	ФедосеевПавел Программа должна вывести два беззнаковых числа чила x и y, удовлетворяющих данной системе. Гарантируется, что такие числа всегда найдутся. Если у системы уравнений несколько решений - выводите любое. При решении задачи запрещается использовать инструкции условной передачи данных и управления. При данном условию есть ли какое то уравнение с помощью которого можно найти x и y при любых значениях остальных переменных?Писать буду на SASM.Я просто слаб в битовых операциях.Просто нужно выразить х как y затем подставить его во второе уравнение.Но вот как незнаю. 0

ФедосеевПавел Модератор 8541 / 4393 / 1651 Регистрация: 01.02.2015 Сообщений: 13,649 Записей в блоге: 9
	12.03.2020, 00:03	16
	Да - таблица в виде двух массивов x и y. А индекс - составляется из битов (a11,a12,a21,a22,b1,b2). 0

murderer 4174 / 1824 / 218 Регистрация: 06.10.2010 Сообщений: 4,111
	12.03.2020, 07:31	20
	Да с кодом я тупанул. Добавлено через 6 минут Verevkin a21 & x = b2 ^ (a22 & y), x = (b2 ^ (a22 & y)) & !a21 + 1 Это ведь всё равно, что утверждать z&x=y x=y&!z+1 Подставим произвольные значения x=0, y=0, z=1 1&0=0 - верно 0=0&!1+1=0&0+1=1 - не верно Добавлено через 23 минуты Мне кажется,что операции & и + в отличие от ^ и ! необратимы. Следовательно решение возможно только перебором. То есть операция x&0 необратимо уничтожит информацию, содержащуюся в x. А вот ^ можно обратить (X^Y)^Y=X. 0

Решить систему уравнений с побитовыми операциями

Решение