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

Сложение по модулю (2^32) -1) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.88
nullpointer
 Аватар для nullpointer
45 / 45 / 5
Регистрация: 30.03.2009
Сообщений: 518
04.02.2014, 00:35     Сложение по модулю (2^32) -1) #1
Добрый вечер! Подскажите как реализовать сложение по модулю ((2^32) -1). Есть текстовый файл. Я считываю его, перевожу считанные данные в биты, в результате получается массив из нулей и единиц. Его размер равен 32. Мне нужно сложить его с другим массивом такого же размера по модулю ((2^32) -1). Есть кое-какие соображения, но естественно делаю неправильно.
C++
1
2
3
4
5
6
7
8
9
10
11
int oneMas[32] = {0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1};
int twoMas[32] = {0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0};
int Res[32];
 
for (int i = 31; i >= 0; i--)
{
    if (oneMas[i] + twoMas[i] < 2)
        Res[i] = oneMas[i] + twoMas[i];
    else
        Res[i] = oneMas[i] + twoMas[i] - 1;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.02.2014, 00:35     Сложение по модулю (2^32) -1)
Посмотрите здесь:

ошибка в функции сложение по модулю два C++
C++ сложение по модулю 2(проблема с массивом bool)
Произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами C++
вычислить произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами C++
Найти произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mf909
96 / 12 / 3
Регистрация: 10.01.2014
Сообщений: 29
04.02.2014, 01:22     Сложение по модулю (2^32) -1) #2
При сложении двух единиц в одном разряде получается в этом разряде 0, но единица переносится на следующий старший разряд, который в данном массиве имеет индекс на 1 меньше.
zelim
77 / 77 / 4
Регистрация: 26.12.2011
Сообщений: 217
04.02.2014, 02:02     Сложение по модулю (2^32) -1) #3
nullpointer,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    int oneMas[32] = {0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1};
    int twoMas[32] = {0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0};
 
    int Res[32] = {0};
 
 
    for (int i = 31; i >= 0; --i)
 
    {
        int s = oneMas[i] + twoMas[i] + Res[i];
    
        if (s < 2)
        
            Res[i] += oneMas[i] + twoMas[i];
    
        else {
            Res[i] = (s==2) ? 0 : 1;
            Res[i-1] = 1;
        }
vovacreme
-16 / 61 / 13
Регистрация: 14.01.2014
Сообщений: 145
04.02.2014, 02:56     Сложение по модулю (2^32) -1) #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include <iterator>
#include <deque>
 
using namespace std;
 
int main()
{
 
    int oneMas[32] = {0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1};
    int twoMas[32] = {0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0};
    deque<int> res;
    int carr = 0;
    for (int i = 31; i >= 0; i--)
    {
        res.push_front( (oneMas[i] + twoMas[i] + carr) % 2);
        carr = oneMas[i] + twoMas[i] + carr > 1 ? 1 : 0;    
    }
    carr ? res.push_front(carr) : 0;
    copy(res.begin(), res.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    system("pause");
}
Добавлено через 31 минуту
zelim, на последней итерации получим выход за пределы массива, при условии s >= 2
nullpointer
 Аватар для nullpointer
45 / 45 / 5
Регистрация: 30.03.2009
Сообщений: 518
04.02.2014, 10:53  [ТС]     Сложение по модулю (2^32) -1) #5
vovacreme, почему то ваш код выдает неправильное значение, проверял записывал два числа в десятичной и двоичной системе и складывал. В десятичной складывал вот так
C++
1
int res = (one + two) & ((1u << 32) - 1);
и результаты совершенно разные получились.

Код zelim работает если цикл вести от 0 до 32, а если в обратном порядке, то получаю сообщение о выходе за пределы.
gunslinger
случайный прохожий
 Аватар для gunslinger
1097 / 715 / 184
Регистрация: 20.07.2013
Сообщений: 1,969
04.02.2014, 15:30     Сложение по модулю (2^32) -1) #6
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
  const n = 32;
  int oneMas[n] = {0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1};
  int twoMas[n] = {0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0};
  int i, temp, Res[n+1] = {0}, ResMod[n];
 
// сложение
  for (i = n-1; i >= 0; i--)
  {
    temp = oneMas[i] + twoMas[i] + Res[i+1];
    Res[i+1] = temp%2;
    Res[i] = temp/2;
  }
 
// результат по модулю 2^32-1
// случай, когда сумма >= 2^32; вычитаем 2^32-1
  while (Res[0])  // можно заменить на if, так как будет максимум один "проход"
  {
    for (i = n-1; i >= 0; i--)
    {
      Res[i+1]--;
      if (Res[i+1] < 0)
      {
        Res[i]--;
        Res[i+1] += 2;
      }
    }
  };
// (частный) случай, когда осталось ровно 2^32-1; "обнуляем"
  temp = 0;
  for (i = 1; i <= n; i++)
    if (Res[i])
      temp++;
  if (temp == n)
    for (i = 1; i <= n; i++)
      Res[i] = 0;
 
  for (i = 1; i <= n; i++)
    ResMod[i-1] = Res[i];
ShadowFirst
54 / 47 / 1
Регистрация: 31.10.2013
Сообщений: 161
04.02.2014, 16:02     Сложение по модулю (2^32) -1) #7
По условию мне не совсем понятно, после сложения ответ может превышать (2^32)-1 или нет. Я почему об этом спросил, если нет то достаточно обойтись двумя переменными unsigned int и заполнять в них биты путем сдвига, а если все таки превышает то есть тип данных long long или в некоторых ОС просто long которая имеет в наличии 8 байт для хранения целого числа и в нем делать по вышеописанному принципу.

А далее ответ получаем путем банального сложения
nullpointer
 Аватар для nullpointer
45 / 45 / 5
Регистрация: 30.03.2009
Сообщений: 518
04.02.2014, 20:55  [ТС]     Сложение по модулю (2^32) -1) #8
gunslinger, вы проверяли его? просто у меня в результате получается единица, что совсем не верно
gunslinger
случайный прохожий
 Аватар для gunslinger
1097 / 715 / 184
Регистрация: 20.07.2013
Сообщений: 1,969
04.02.2014, 21:28     Сложение по модулю (2^32) -1) #9
Проверял (на Builder). Res содержит 33 бита ("левый" нужен для хранения 1 при "переполнении").
ResMod - 32 бита (результат по модулю 2^32-1). Он тебе и нужен.
Для исходных данных получаем
00000010000001010000010100000101
P.S.: если что, смотри в сторону инициализации "правого" бита Res. Хотя, наверно, вряд ли дело в этом.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.02.2014, 00:38     Сложение по модулю (2^32) -1)
Еще ссылки по теме:

C++ Сложение по модулю 2 и разбиение массива на 8
Сложение по модулю 2 C++
Как выполнить сложение по модулю 2^64+13 C++

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

Или воспользуйтесь поиском по форуму:
nullpointer
 Аватар для nullpointer
45 / 45 / 5
Регистрация: 30.03.2009
Сообщений: 518
05.02.2014, 00:38  [ТС]     Сложение по модулю (2^32) -1) #10
gunslinger, да, виноват, просто вывел неправильно
Yandex
Объявления
05.02.2014, 00:38     Сложение по модулю (2^32) -1)
Ответ Создать тему
Опции темы

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