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

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

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

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

Code
1
2
3
(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

Code
1
2
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
{$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++
1
2
3
4
5
6
7
8
9
10
11
    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.

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

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

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

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

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

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

ФедосеевПавел Модератор 8665 / 4502 / 1670 Регистрация: 01.02.2015 Сообщений: 13,930 Записей в блоге: 13
	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). А можете их просто перебрать в цикле. 0

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

ФедосеевПавел Модератор 8665 / 4502 / 1670 Регистрация: 01.02.2015 Сообщений: 13,930 Записей в блоге: 13
	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. Вот и нет условных переходов и присвоений. Как вы будете распознавать отсутствие решения без условных переходов - не понятно. Без шуток - что по поводу решения думают сокурсники и преподаватель? Какие варианты? 0

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

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

Решение