Форум программистов, компьютерный форум CyberForum.ru

Битовые операции, найти ошибку в коде - C++

Восстановить пароль Регистрация
 
 
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
13.03.2014, 12:47     Битовые операции, найти ошибку в коде #1
Написал немного коду с битовыми операциями, чтобы заменять биты, но почему то работает не так как хотелось. Комментарии все в коде. В HEX редакторе получаются в основном одни FF, т.е. байты заполненные единичками. Алгоритм должен быть обратным, но не выходит.
key это интовская переменная
array это байтовый массив содержащих исходные данные (QByteArray array)
itog это байтовый массив измененных данных

C++
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
void MainWindow::sh(int n)
{
 
int razr_0 = 1, razr_1 = 2, razr_3 = 8, razr_4 = 16; //для проверки значения тех разърядов которые подлжеат XOR
 
for(int i = 0; i < 8; i++) {
 
    int razr0 = razr_0 & key; //проверяем значения бит нужных разърядов
    int razr1 = razr_1 & key;
    int razr3 = razr_3 & key;
    int razr4 = razr_4 & key;
 
        int mlad_bit = razr_0 & array[n]; //младший бит элемента массива из файла
        array[n] = array[n] >> 1; //сдвигаем вправо, чтобы на следующем шаге опять проверять младший бит
 
        int nov_bit = razr4 ^ razr3 ^ razr1 ^ razr0;
        if(nov_bit == 1)
        {
            //получаем новый бит == 1
            key = key >> 1; //удаляем младший бит
            key = key | 2048; //добавляем старший разъряд
        }
        else
        {
            //получаем новый бит == 0
            key = key >> 1; //удаляем младший бит
        }
 
 
        //********************************************************************************
        int nov_kod_bit = mlad_bit ^ razr0;
        if(nov_kod_bit == 0)
        {
            itog[n] = itog[n] | 0;
            itog[n] = itog[n] >> 1;
        }
        else
        {
            itog[n] = itog[n] | 128;
            itog[n] = itog[n] >> 1;
        }
 
 
 
    }
}
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
13.03.2014, 15:22     Битовые операции, найти ошибку в коде #2
Цитата Сообщение от танкист34 Посмотреть сообщение
получаются в основном одни FF
А что должно получаться? Что должен содержать массив itog[]?
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
13.03.2014, 15:27  [ТС]     Битовые операции, найти ошибку в коде #3
Alex5, я вас не совсем понял=)) не имеет значения какие биты в нём окажутся, так как это зависит от входного массива, думаю, это и так видно. Проблема в том, что почему то этот код не обратим.
Поясняю: если мы массив itog подадим на вход, то array мы не получим, хотя должен он получиться, но не получается. Может у меня глаз замылился и не вижу в чём ошибка.
Если нет у вас вариантов, то подскажите, пожалуйста, есть ли отладчик под Qt типа TD под DOS, чтобы каждый шаг отслеживать в HEX коде?

может вам будет интересно как я на вход подаю массив:
C++
1
2
3
4
for(int i = 0; i < "размер массива в байтах"; i++)
{
       sh(i);
}
PS: результат выходного массива ещё зависит от key
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
13.03.2014, 15:55     Битовые операции, найти ошибку в коде #4
танкист34, я спрашиваю не о конкретных битах, а об правиле(алгоритме), как itog[] зависит от array[].
Чтобы найти ошибку в программе, надо знать исходную задачу.
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
13.03.2014, 16:06  [ТС]     Битовые операции, найти ошибку в коде #5
берём биты: первый, второй, четвёртый и пятый от key. Их ксорим XOR.
Полученное значение(бит) добавляем в переменную key, в старший разъряд. Так как key 12 разърядный, то я и выбрал значение 2048 длля установки 1 в 12 разъряд(по сути это 11 разряд, если от нуля считать).
А младший разъряд key перед потерей (всвязи со сдвигом), так как кол-во разърядов в key менять нельзя, XORим c младшим битом исходного массива и сохраняем в itog. Вот и всё.

Если кратко: то от key берутся указанные разряды, ксорятся, и результат в старший разъряд, а младший ксорится с младшим битом исходного массива и удаляется. И так до конца.

И получается, что это дело симметричное, я даже на бумаге раскладывал, а вот на машине не получается.
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
13.03.2014, 17:24     Битовые операции, найти ошибку в коде #6
Цитата Сообщение от танкист34 Посмотреть сообщение
C++
1
2
3
4
int razr0 = razr_0 & key; //проверяем значения бит нужных разърядов
 int razr1 = razr_1 & key;
 int razr3 = razr_3 & key;
 int razr4 = razr_4 & key;
Пример. key == 31 ( в двоичной записи 11111 ). Тогда получим razr0 : 1, razr1 : 2, razr2 : 8, razr3 : 16.
Значения razr0, razr1, razr2, razr3 - либо 0, либо степени 2.
Цитата Сообщение от танкист34 Посмотреть сообщение
C++
1
2
int nov_bit = razr4 ^ razr3 ^ razr1 ^ razr0;
 if(nov_bit == 1)
Возможные значения nov_bit : 1, 2, 8, 16, 1+2, 1+8, 8+16 и т.п. Что Вы думаете об этом?
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
13.03.2014, 17:50  [ТС]     Битовые операции, найти ошибку в коде #7
а точно, я вообще капец запутался. Я предпологал, что единица вначале, хотя знал что она в нужном разъряде. Есть предположения исправить:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if(razr0 == 1) 
        kol_1 = kol_1 + 1;
        else kol_0 = kol_0 + 1;
        
        if(razr1 == 2)
            kol_1 = kol_1 + 1; 
        else kol_0 = kol_0 + 1;
        
        if(razr3 == 8)
            kol_1 = kol_1 + 1; 
        else kol_0 = kol_0 + 1;
        
        if(razr4 == 16)
            kol_1 = kol_1 + 1; 
        else kol_0 = kol_0 + 1;
Т.е. подсчитаем сколько всего единиц и нулей, а потом делаем вывод что получится. Если Нулей больше единиц или единиц больше нулей, то результат XOR будет 1, иначе 0. Но так тоже не робит
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
13.03.2014, 18:11     Битовые операции, найти ошибку в коде #8
Какое начальное значение имеет itog[]? В приведённом коде есть операции вида itog[n] = itog[n] | 128; Но ведь результат зависит от исходного значения.
Цитата Сообщение от танкист34 Посмотреть сообщение
кол-во разърядов в key менять нельзя
Имеется в виду кол-во ненулевых битов?
Цитата Сообщение от танкист34 Посмотреть сообщение
C++
1
2
            //получаем новый бит == 0
            key = key >> 1; //удаляем младший бит
Может случиться, что младший бит равен 1, удаляется. А новый бит не добавляется.

Цитата Сообщение от танкист34 Посмотреть сообщение
есть ли отладчик под Qt типа TD
Если нет отладчика, можно добавить вывод на экран ( printf(), cout ) значений key, itog[] ( после каждого шага цикла, например ).
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
13.03.2014, 18:20  [ТС]     Битовые операции, найти ошибку в коде #9
Alex5, 1. все элементы массива itog по идее обнулены. следовательно или точно утсановит 1.
2. не только не нулевых, ведь число из 12 разърядов может и нули содержать. ex: 111000111000.
поэтому сдвиг на 1 и применяется, чтобы один добавить, а один удалить в итоге всегда 12 разърядов.
3. да, вот здесь и я думаю, не знаю до скольки надо счётчик цикла установить, либо до 7, либо до 8ми.
4. он есть, наверно, просто Qt для меня новинка. А cout это дедовский метод, но он только для консольных приложений, а я использую GUI.
Был бы отладчик, я бы уже давно сделал, там все кишки видно.
Спасибо, что помогаете.
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
13.03.2014, 19:57     Битовые операции, найти ошибку в коде #10
Если сдвиг >> выполнять после добавления бита, то старший бит всегда будет нулевым. А информация о бите, установленном при i==0, будет потеряна.
Вот так, действительно, применяя вычисления к itog[], получаем исходный массив.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
 if(nov_kod_bit == 0)
{
    // ... 
}
else
{
    itog[n] = itog[n] >> 1;
    itog[n] = itog[n] | 128;
    
    // error 
    //itog[n] = itog[n] | 128;
    //itog[n] = itog[n] >> 1;
}
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
14.03.2014, 03:14  [ТС]     Битовые операции, найти ошибку в коде #11
Alex5, всё равно не обратимо получается
вот функция:
C++
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
void MainWindow::sh(int n)
{
 
int razr_0 = 1, razr_1 = 2, razr_3 = 8, razr_4 = 16; //для проверки значения тех разърядов которые подлжеат XOR
 
for(int i = 0; i < 8; i++) {
 
    int razr0 = razr_0 & key; //проверяем значения бит нужных разърядов
    int razr1 = razr_1 & key;
    int razr3 = razr_3 & key;
    int razr4 = razr_4 & key;
 
        int mlad_bit = razr_0 & array[n]; //младший бит элемента массива из файла
        array[n] = array[n] >> 1; //сдвигаем вправо, чтобы на следующем шаге опять проверять младший бит
 
                int kol_1 = 0; int kol_0 = 0;
 
                if(razr0 == 1) //здесь проверяем младший бит ключа
                kol_1 = kol_1 + 1;
                else kol_0 = kol_0 + 1;
 
                if(razr1 == 2)
                    kol_1 = kol_1 + 1;
                else kol_0 = kol_0 + 1;
 
                if(razr3 == 8)
                    kol_1 = kol_1 + 1;
                else kol_0 = kol_0 + 1;
 
                if(razr4 == 16)
                    kol_1 = kol_1 + 1;
                else kol_0 = kol_0 + 1;
 
                if(kol_1 > kol_0 || kol_0 > kol_1)
                {
                    //получаем новый бит == 1
                    key = key >> 1;
                    key = key | 2048;
                }
                else if (kol_1 == kol_0)
                {
                    //получаем новый бит == 0
                    key = key >> 1;
                    key = key | 0;
 
                }
 
        //********************************************************************************
        int nov_kod_bit = mlad_bit ^ razr0;
 
        if(nov_kod_bit == 0)
        {
            itog[n] = itog[n] >> 1;
            itog[n] = itog[n] | 0;
        }
        else
        {
            itog[n] = itog[n] >> 1;
            itog[n] = itog[n] | 128;
        }
 
    }
 
}
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
14.03.2014, 14:29     Битовые операции, найти ошибку в коде #12
Цитата Сообщение от танкист34 Посмотреть сообщение
Alex5, всё равно не обратимо получается
Может быть, значение key не устанавливаете в исходное значение.
Где у Вас в коде, key = ...; for( i ... ) itog[i] = 0; ? (Кстати, key, array[] - где они объявлены? Это члены класса MainWindow?)
Цитата Сообщение от танкист34 Посмотреть сообщение
C++
1
void MainWindow::sh(int n)
Как Вы "подаёте на вход" itog[]? Ведь у функции MainWindow::sh() исходные данные берутся из array[], а результат записывается в itog[].
Может быть, стоит добавить array[], itog[], key в параметры функции?
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
14.03.2014, 15:20  [ТС]     Битовые операции, найти ошибку в коде #13
key точно устанавливается, так как я же данные полученные сохраняю в файл, а потом их обратно считываю(перезапуская программу). Щас я код в более приемлемый вид соберу и скину, а вообще меня смущает счётчик цикла я не пойму на 8 его ставить или на 7.
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
16.03.2014, 16:45  [ТС]     Битовые операции, найти ошибку в коде #14
Alex5, вот измененная функция, но проблема сохраняется, хотя сейчас проблема с увелечением первоначальных данных ушла, но исходные данные по этому алгоритму назад не получаются.
C++ (Qt)
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
char MainWindow::sh(QByteArray array, int n) //на вход исходный массив и индекс байта
{
int razr_0 = 1, razr_1 = 2, razr_3 = 8, razr_4 = 16; //для проверки значения тех разърядов которые подлжеат XOR
char simv;
 
for(int i = 0; i < 8; i++) {
 
    int razr0 = razr_0 & key; //проверяем значения бит нужных разърядов
    int razr1 = razr_1 & key;
    int razr3 = razr_3 & key;
    int razr4 = razr_4 & key;
 
        int mlad_bit = razr_0 & array[n]; //младший бит элемента массива из файла
        array[n] = array[n] >> 1; //сдвигаем вправо, чтобы на следующем шаге опять проверять младший бит
 
                int kol_1 = 0; int kol_0 = 0;
 
                if(razr0 == 1) //здесь проверяем младший бит ключа
                kol_1 = kol_1 + 1;
                else kol_0 = kol_0 + 1;
 
                if(razr1 == 2)
                    kol_1 = kol_1 + 1;
                else kol_0 = kol_0 + 1;
 
                if(razr3 == 8)
                    kol_1 = kol_1 + 1;
                else kol_0 = kol_0 + 1;
 
                if(razr4 == 16)
                    kol_1 = kol_1 + 1;
                else kol_0 = kol_0 + 1;
 
                if(kol_1 > kol_0 || kol_0 > kol_1)
                {
                    //получаем новый бит == 1
                    key = key >> 1;
                    key = key | 2048;
                }
                else if (kol_1 == kol_0)
                {
                    //получаем новый бит == 0
                    key = key >> 1;
                    key = key | 0;
                }
        //********************************************************************************
        int nov_kod_bit = mlad_bit ^ razr0;
 
        if(nov_kod_bit == 0)
        {
            simv = simv >> 1;
            simv = simv | 0;
        }
        else
        {
            simv = simv >> 1;
            simv = simv | 128;
        }
 
    }
 
   return simv;
 
}
вызываю вот так:
C++ (Qt)
1
2
3
4
5
6
7
8
9
for(int n = 0; n < size_array; n++)
        {
            itog[n] = 0;  //предварительное обнуление
        }
 
        for(int n = 0; n < size_array; n++)
        {
           itog[n] = sh(array, n);
        }
Добавлено через 7 минут
переменную simv пробывал инициализировать нулём, результата также не последовало (в чём магия я не понимаю)
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
16.03.2014, 16:52     Битовые операции, найти ошибку в коде #15
Цитата Сообщение от танкист34 Посмотреть сообщение
берём биты: первый, второй, четвёртый и пятый от key. Их ксорим XOR.
Полученное значение(бит) добавляем в переменную key, в старший разъряд.
ну и как это как 4 бита превращаются в 1
это сложение вычитание И ИЛИ?
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
16.03.2014, 17:18  [ТС]     Битовые операции, найти ошибку в коде #16
ValeryS, можете ещё раз написать, не совсем понятна фраза "ну и как это как" и "это сложение вычитание И ИЛИ'. Операнды все в стандарте определены, которые я использую, если вы про это. А если вам надо пояснить, какой операнд, что значит : | побитовое ИЛИ, & побитовое И, ^ исключающее ИЛИ.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
16.03.2014, 18:35     Битовые операции, найти ошибку в коде #17
танкист34,
еще раз это,я у тебя хочу спросить
Цитата Сообщение от танкист34 Посмотреть сообщение
берём биты: первый, второй, четвёртый и пятый от key. Их ксорим XOR.
Полученное значение(бит) добавляем в переменную key, в старший разъряд.
4 бита итого 16 комбинаций
как из них получить один бит когда он равен 1 и когда равен 0???

Добавлено через 9 минут
Цитата Сообщение от танкист34 Посмотреть сообщение
int razr_0 = 1, razr_1 = 2, razr_3 = 8, razr_4 = 16;
эти волшебные числа заменяются вот такой конструкцией
C++
1
int razr_0 = 1<<0, razr_1 = 1<<1, razr_3 = 1<<3, razr_4 = 1<<4;
а равно и это
Цитата Сообщение от танкист34 Посмотреть сообщение
key = key | 2048;
C++
1
key = key | (1<<11);
а можно и вот так сделать
C++
1
2
3
4
5
6
7
const r1=0;
const r2=1;
const r3=3;
const r4=4;
const rA=11;
......................................
int razr_0 = 1<<r1, razr_1 = 1<<r2, razr_3 = 1<<r3, razr_4 = 1<<r4;
..............................
key = key | (1<<rA);[/CPP]

тогда если будут нужны другие разряды то просто в одном месте поменяешь а не будешь лазить по всему листингу
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
16.03.2014, 18:48  [ТС]     Битовые операции, найти ошибку в коде #18
ValeryS,
"эти волшебные числа заменяются вот такой конструкцией"
меня сейчас мало интересует такая запись кода, тем более суть не меняется, а запись длиньше и не понятна на восприятие.
"еще раз это,я у тебя хочу спросить"
там если посмотреть, то можно увидеть условие. Если нулей больше чем единиц, то будет единица, и наоборот. А если нулей и единиц поровну, то будет ноль. Причём здесь 16 комбинаций?! Если вы про порядок следования, то он не имеет значения. То что 16 комбинаций это не говорит о том, что есть 16 вариантов.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
16.03.2014, 19:15     Битовые операции, найти ошибку в коде #19
Цитата Сообщение от танкист34 Посмотреть сообщение
там если посмотреть, то можно увидеть условие.
это вот это что ли?
Цитата Сообщение от танкист34 Посмотреть сообщение
int nov_bit = razr4 ^ razr3 ^ razr1 ^ razr0;
if(nov_bit == 1)
у тебя то сработает если в key будет число 00x01 допустим 00001
никаких больше меньше
смотри
int razr0 = razr_0 & key; 00001& 00001=1;
int razr1 = razr_1 & key; 00001& 00010=0
int razr3 = razr_3 & key; 00001& 01000=0
int razr4 = razr_4 & key; 00001& 10000=0
теперь
int nov_bit = razr4 ^ razr3 ^ razr1 ^ razr0;

0^0^0^0=1
другое число 10000
int razr0 = razr_0 & key; 10000& 00001=0;
int razr1 = razr_1 & key; 10000& 00010=0
int razr3 = razr_3 & key; 10000& 01000=0
int razr4 = razr_4 & key; 10000& 10000=10000

int nov_bit = razr4 ^ razr3 ^ razr1 ^ razr0;

10000^0^0^0=10000

единиц меньше чем 0 но условие уже не выполняется
ты же разряды не подгоняешь
да и XOR здесь неуместен он сможет проверить только четное нечетное количество единиц

вот примерно как нужно

C++
1
2
3
4
5
6
7
8
9
int nov_bit=key&0x01; // выделяем младший бит
nov_bit=nov_bit+((key>>1)&0x01); // сдвигаем чтобы второй бит стал младшим выделяем его и плюсуем
nov_bit=nov_bit+((key>>3)&0x01); // сдвигаем чтобы четвертый бит стал младшим выделяем его и плюсуем
nov_bit=nov_bit+((key>>4)&0x01); // сдвигаем чтобы пятый бит стал младшим выделяем его и плюсуем
 
if(nov_bit>2)
 // количество единиц больше 0
else
// количество единиц меньше или равно количеству нулей
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2014, 20:43     Битовые операции, найти ошибку в коде
Еще ссылки по теме:

Битовые операции и операции смещения языка С C++
Арифметические операции, найти ошибку в коде C++
C++ Битовые операции

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
16.03.2014, 20:43     Битовые операции, найти ошибку в коде #20
Цитата Сообщение от танкист34 Посмотреть сообщение
вызываю вот так:
C++
1
2
3
4
5
6
7
8
9
for(int n = 0; n < size_array; n++)
 {
 itog[n] = 0; //предварительное обнуление
 }
/* Чему равно key в этот момент для 1-го и для 2-го вызова?*/
for(int n = 0; n < size_array; n++)
 {
 itog[n] = sh(array, n);
 }
танкист34, можете привести конкретный численный пример?
Вход: key, array[], itog[]. Результат на выходе: key, array[], itog[]. Конкретные численные значения?
Теперь хотим восстановить исходный массив.
Вход: key, array[], itog[]. Результат на выходе: key, array[], itog[].
Yandex
Объявления
16.03.2014, 20:43     Битовые операции, найти ошибку в коде
Ответ Создать тему
Опции темы

Текущее время: 15:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru