Как реализовать побитовый сдвиг чисел, которые записаны как строки ( длинные числа хранятся в строках)?

Question

[Sunter]

Есть число "4294967296" 2^32 надо получить побитового сдвинув длинное число 2^64. Деление, умножение длинных чисел нельзя int-ых можно.

Comments

[Петр]

Школьная математика, деление в столбик на 2 и результат сразу сдвигаете в любую сторону.

Answer 1

[Mercury13]

Как я понял, вы пишете калькулятор. В десятичной системе, чтобы вычисленное калькулятором совпало с вычисленным на бумажке — на что ещё десятичная система? Есть два варианта.
1. Преобразовать в двоично-длинный формат (2⁶⁴ не входит в long long), сдвинуть, вернуть.
2. Получить 2³² в десятично-длинном формате, и перемножить.
3. В зависимости от величины сдвига поступить так или этак: например, сдвиги на 1/2/3 вторым способом, а на 4 и больше — первым.
Думайте сами, что лучше.

Comments

[Sunter]

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

[Mercury13]

Sunter, Пардон. Преобразование из строкового в родной работает по схеме Горнера:
((((0·10)+4)·10+2)·10+9)…

т.е. цикл sum := 10sum + x[i]

А вот наоборот, из родного в строковый — нужно деление на 10.

[Mercury13]

Sunter, Поскольку у вас точность длинная (выше 2⁶⁴), нормального преобразования из родного в строковый не найдётся: один хрен где-то будем делить на 10. Алгоритмы деления на 10 если и существуют, то страшны как чёрт и сильно полагаются на ограниченную величину числа.

«Деление, умножение длинных чисел нельзя» — это, вероятно, значит, что вам самим придётся реализовать работу с длинными числами, а не драть на стороне.

Answer 2

[mayton2019]

Сдвиг на 2^64 это я так понимаю что сдвиг влево на 64 бита. Иначе смысла бы не было. Получили бы ноль.

Сдвиг влево - это умножение на 2 в степени числа сдвигов. Тоесть

2^32 * 2^64 = 2^96

(при умножении степеней показатели складываются)

Comments

[Sunter]

Дополнил вопрос, тем что умножения длинных чисел не используется, надо реализовать их побитовый сдвиг

[Wataru]

Sunter, У вас нет умножения длинных чисел, у вас есть умножение длинного на короткое (2^64). Если за раз не помещается, можно 2 раза домножить на 2^32.

Вообще, если база не степень двойки, то все плохо. Я так понял, у вас в строке цифры хранятся, так что база у вас 10. Сдвиги можно реализовать только умножением на 2 в какой-то степени.

[Sunter]

Wataru, как лучше хранить длинные числа, чтобы реализовать умножение длинных чисел через побитовый сдвиг

[Wataru]

Sunter, В бинарном виде. У вас массив интов. Каждый инт хранит от 0 до 2^32 - 1. Фактически, число записано в 2^32-ичной системе счисления.
При выводе такого числа, надо делить его на короткие вроде 1000000000. Остатки выводить. Все, кроме последнего с ведущими нулями до 9 цифр. И в обратном порядке.
При сдвиге у вас есть перенос с младших разрядов. Сдвигаете текущую "цифру" влево, OR-ите с переносом. 32 младших бита в текущую цифру, оставшиеся - в перенос.
Складывать как обычно, только смотреть, чтобы переполнения не было - надо использовать int64 для промежуточных значений.
С умножениями чуть сложнее - надо или промежуточный массив из int64 завести, или базу уменьшать, чтобы аккумуляторы не переполнялись.

[mayton2019]

Автор дописал уточнение

Деление, умножение длинных чисел нельзя int-ых можно.

Как нам теперь быть? Длинные нельзя но int можно. Имется в виду что нам доступна только арифметика 32х разрядных чисел. А надо оперировать до 96 битных.

Правильно ли я понял?

Answer 3

[Wataru]

Из комментариев понятно, что это вы так пытаетесь умножение двух длинных чисел через сдвиги реализовывать. Соответственно, у вас сдвиги тоже длинные.

Можно сдвигать не двоичные цифры, а десятичные. Или вообще любые. Тогда помимо сдвига еще появляется умножение на цифру. Такой сдвиг в строке из цифр - это просто сдвиг всей строки на нужное количество позиций. Саму сдвинутую строку вам не надо и получать, в общем-то.

Основной цикл будет вроде

for (int i = 0; i < a.length(); ++i) {
  for (int j = 0; j < b.length(); ++j) {
     c[i+j] += a[i] * b[j];
  }
}

В этом коде i+ - это и есть сдвиг. a[i] - это цифра на которую приходится домножать. а b[j] - это собственно само сдвигаемое и прикладываемое число.