Преобразование двоичного числа в десятичное со знаком

В Калькуляторе Windows попробовал перевести "-1" в двоичное представление и получил
1111111111111111111111111111111111111111111111111111111111111111. Затем опять попробовал перевести в десятичное, получил 18446744073709551615. Хотел бы сделать программу, которая правильно переводила бы двоичное представление в десятичное. Например, указал двоичное представление 1011111111111111111111111111111111111111111111111111111111111111, получил бы правильное целое число со знаком, а не 13835058055282163711.
Попробовал сам написать программу:

#include <iostream>
#include <string>
 
using namespace std;
 
int strtoint(string sbit) {
  int i, multi = 1, number = 0;
  for(i = sbit.length(); i; i--, multi *=2 ) {
    if(sbit[i-1] == '1')
      number += multi;
  } //for
  return number;
}
 
void main(int argc, char* argv[]) {
  int narr[] = {-1, 1, -2, 2, -4, 4, -8, 8, -16, 16, -64, 64, -128, 128, -32767, 32767}, i = 0, j = 1, num;
  char sbit[33];
  string str, strnew;
  while(narr[i]) {
     sbit[0]  = 0;
     sbit[32] = 0;
    _itoa(narr[i], sbit, 2);
    str = sbit;
    while(str.length() < 32) {
      str.insert(0, "0");  
    }
    strnew = str;
    if(strnew[0] == '1') {
      for(j = 0; j < strnew.length() - 1; j++) {
        if(strnew[j]=='1')
          strnew[j] = '0';
      } // for j
      if(strnew[strnew.length()]=='1')
        strnew[strnew.length()] = '0';
      num = -1 * strtoint(strnew);
    }  // if(strnew[0] == '1'
    else {
      num = strtoint(strnew);
    }
    cout <<  narr[i] << "\t" << num << endl;
    i++;
  } // while
  cin.get();
}

В массив narr могут добавляться другие знчения, поэтому хотелось бы не задавать жестко число элементов в нем. Вижу следующие ошибки:
1. Неправильно прохожу массив narr, появляются мусорные значения. Хотелось бы понять, как правильно проходить массив при такой его инициализации.
2. Неправильно работаю с дополнительным битом, полученные значения для отрицательных чисел неверны.
Подскажите,пожалуйста, как мне правильно обойти массив и правильно конвертировать дополнительный код для отрицательного числа.

1.

long len = sizeof(narr)/sizeof(narr[0]);
for ( long i = 0; i < len; i++ )

Изучите уже наконец битовую арифметику:

long strtoint(string sbit)
{
  int i, len;
  long number=0;
  len=sbit.length();
  for(i=0; i<len; i++)
  {
    number<<=1;
    if(sbit[i] == '1') number |= 1;
  }
  // Расширение знакового бита
  // Нужно если строка содержит не все биты (длина строки не равна разрядности числа)
  // "011" - будет 3, "11" - будет -1
  if(len!=sizeof(number)*8)
  {
    number<<=sizeof(number)*8-len;
    number>>=sizeof(number)*8-len;
  }
  return number;
}

Сообщение отредактировано: cppasm - 11.02.11, 09:52

cppasm, там 65 по 1 =) long мала будет, в MSVC вообще long = int

Дык bitset! И нафиг строки и long'и.

1...1 - это так называемый дополнительный код числа. Для перевода в десятичную нужно сделать так:
1 - конвертировать все биты: 0->1, 1->0
2 - прибавить 1 в двоичной системе.
3 - переводить в десятичную
4 - поставить спереди минус.

Цитата ss @ 11.02.11, 10:46

Дык bitset! И нафиг строки и long'и.

#include <iostream>
#include <bitset>
 
int main ()
{
    std::bitset<33> bits;
    bits.set();
    bits.to_ulong();
    return 0;
}

Падает =)

Сообщение отредактировано: like-nix - 11.02.11, 11:00

_Xoflo();   // fail if any high-order words are nonzero

Ты б ещё 500 бит в ulong упихать попытался

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

Добавлено 11.02.11, 11:26
Кстати у буста тоже есть bitset, там функционала побольше

Добавлено 11.02.11, 11:26
арефметические операции например можно выполнять, только у меня пока не получается =)

Добавлено 11.02.11, 11:28
Делаю так

#include <iostream>
#include <boost/dynamic_bitset.hpp>
 
int main ()
{
    boost::dynamic_bitset<> x1(34), x2(34);
 
    x1[31] = 1;
    x2[30] = 1;
 
    std::cout << x1.to_ulong() << std::endl;
    std::cout << x2.to_ulong() << std::endl;
 
    boost::dynamic_bitset<> x3(34);
    x3 = x1 - x2;
    std::cout << x3.to_ulong() << std::endl;
 
    return 0;
}

А x3 всеравно = x1 =)

Сообщение отредактировано: like-nix - 11.02.11, 11:30

Цитата like-nix @ 11.02.11, 11:17

ss, подскажите тогда как перевести из bitset в десятичную систему

перевести-то недолго - делать с этим будет нечего, кроме как осознавать, что вот тута в памяти у меня большое-большое число лежит, которое прочитать некуда

Цитата like-nix @ 11.02.11, 11:17

или хотябы в строку число десятичной системы

кроме как реализовывать арифметику для строк - не знаю. В HEX - там лего, там дааа, а в десятеричную...
Вобщем, погорячился я.

Цитата like-nix @ 11.02.11, 11:17

перевести-то недолго - делать с этим будет нечего, кроме как осознавать, что вот тута в памяти у меня большое-большое число лежит, которое прочитать некуда

я сам написал не подумав. Учитывая что все в компе в двоичной системе хранится

Добавлено 11.02.11, 11:49
битсеты вполне могут подойти главное найти нормальный способ представления числа в другие системы счисления. Я сейчас смотрю библиотеку crypto там вроде тоже можно с большими числами работать.

Цитата like-nix @ 11.02.11, 10:33

cppasm, там 65 по 1 =) long мала будет, в MSVC вообще long = int

Там 64 бита, а не 65. long long (или __int64 на крайний случай) хватит.

Добавлено 11.02.11, 12:04

Цитата LaptevVV @ 11.02.11, 10:48

1...1 - это так называемый дополнительный код числа. Для перевода в десятичную нужно сделать так:
1 - конвертировать все биты: 0->1, 1->0
2 - прибавить 1 в двоичной системе.
3 - переводить в десятичную
4 - поставить спереди минус.

Во первых это называется инвертировать, а во-вторых наоборот всё делать надо.
Отрицательное число - это инверсия положительного плюс 1.
Соответственно надо вычесть единицу и потом инвертировать, к полученному приписать спереди минус.
Хотя по сути это одно и то же получается.

Сообщение отредактировано: cppasm - 11.02.11, 12:10

Строго говоря, Стандарт допускает любое из 3-х представлений отрицательных: прямое, обратное и дополнительное.

Цитата 3.9.1 Fundamental types

7. Types bool, char, wchar_t, and the signed and unsigned integer types are collectively called integral types.⁴³⁾ A synonym for integral type is integer type. The representations of integral types shall define values by use of a pure binary numeration system.⁴⁴⁾ [Example: this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types. ]

---

⁴³⁾ Therefore, enumerations (7.2) are not integral; however, enumerations can be promoted to int, unsigned int, long, or unsigned long, as specified in 4.5.
⁴⁴⁾ A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral power of 2, except perhaps for the bit with the highest position. (Adapted from the American National Dictionary for Information Processing Systems.)

Т.о. декларируется двоичная система счисления для репрезентации значений целых типов, у которых знаковый бит, если он есть, самый старший. Но вот как именно он вносит свой вклад, не декларируется.

Добавлено 11.02.11, 12:52
Это C++. То же для C:

Цитата 6.2.6.2 Integer types

2. For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. There need not be any padding bits; there shall be exactly one sign bit. Each bit that is a value bit shall have the same value as the same bit in the object representation of the corresponding unsigned type (if there are M value bits in the signed type and N in the unsigned type, then M ≤ N). If the sign bit is zero, it shall not affect the resulting value. If the sign bit is one, the value shall be modified in one of the following ways:

• the corresponding value with sign bit 0 is negated (sign and magnitude);
• the sign bit has the value -(2^N) (two’s complement);
• the sign bit has the value -(2^N - 1) (one’s complement).

Which of these applies is implementation-defined, as is whether the value with sign bit 1 and all value bits zero (for the first two), or with sign bit and all value bits 1 (for one’s complement), is a trap representation or a normal value. In the case of sign and magnitude and one’s complement, if this representation is a normal value it is called a negative zero.

В Crypto++ можно работать с очень большими числами.

    Integer i1("9999999999999999999999999999999999999999999999999");
    Integer i2("9999999999999999999999999999999999999999999999998");
    std::cout << i1 - i2 << std::endl;

Добавлено 11.02.11, 13:37
Еще наткнулся на упоминания boost::bigint, но так и не нашел где можно его взять.

Добавлено 11.02.11, 13:42
мысль закончу позже надо работать =)

Сообщение отредактировано: like-nix - 11.02.11, 13:42

cppasm, Ваш код работает. А вот с битовой арифметикой у меня проблемы, никак не доходит. Ваш код

 number<<=1;
    if(sbit[i] == '1') number |= 1;

и

if(len!=sizeof(number)*8)   {
    number<<=sizeof(number)*8-len;
    number>>=sizeof(number)*8-len;
  }

для меня не очень понятен. Если не очень сложно, прокомментируйте, пожалуйста. А как перебрать массив, чтобы не появлялись лишние значения?

Цитата tumanovalex @ 11.02.11, 18:34

number<<=1;
if(sbit[i] == '1') number |= 1;

Ты число собираешь побитово.
Когда надо добавить ещё один бит - всё что у тебя уже есть сдвигаешь на один разряд влево.
При этом добавляется ещё один бит и он равен нулю.
Если в массиве у тебя единица - устанавливаешь новый бит в единицу при помощи ИЛИ.

Цитата tumanovalex @ 11.02.11, 18:34

if(len!=sizeof(number)*8)
{
    number<<=sizeof(number)*8-len;
    number>>=sizeof(number)*8-len;
}

Здесь смотрим - если в массиве было такое же количество бит как и в переменной-результате, ничего делать не надо.
Код выполняется если в массиве бит меньше чем разрадность переменной-результата (или больше, хотя это не предусмотрено).
Лучше заменить на:

if(len<sizeof(number)*8)
{
    number<<=sizeof(number)*8-len;
    number>>=sizeof(number)*8-len;
}

Для простого примера - допустим результат у тебя в char 8 бит, а передали только 3 символа в строке.
Допустим передали -1 как "111".
Тогда после преобразования ты получишь 00000111 - это 7.
Чтобы получить правильный знаковый результат нам надо размножить знаковый бит (старший) в старшие разряды.
Самый простой способ - сделать это арифметическим сдвигом (битовый сдвиг для знаковых чисел).
Сдвигаем влево на 5 бит, получим 11100000.
Теперь сдвигаем вправо на 5 бит - т.е. по сути возвращаем число на место, но при этом арифметический сдвиг новые биты слева заполняет знаковым битом.
Получаем 11111111 - т.е. -1 как и хотели.

И в моём коде везде long можно заменить на long long или __int64 - тогда можно будет преобразовывать до 64 бит, а так как есть только 32.
Если в строке больше символов, то используются только младшие.
Т.е. в моём коде результат 32 бита, если передать 64 символа в строке - в результат сконвертируется только 32 младших бита.

Сообщение отредактировано: cppasm - 11.02.11, 19:35

Спасибо большое за подробное объяснение! Вроде бы все понятно, но вот самому до этого додуматься, к сожалению, не удалось. Остался только один вопрос: почему при выводе элементов массива narr выводится мусор - числа более 32767? Я подсчитал - выводится кроме заданных при инициализации чисел еще 11 чисел!

Сообщение отредактировано: tumanovalex - 12.02.11, 08:11

Ну это вообще элементарно

Цитата tumanovalex @ 11.02.11, 07:47

int narr[] = {-1, 1, -2, 2, -4, 4, -8, 8, -16, 16, -64, 64, -128, 128, -32767, 32767}, i = 0, j = 1, num;
// ...
while(narr[i])
{
    // ...
}

У тебя цикл закончится когда в массиве встретится элемент равный нулю.
А он у тебя там есть? Правильно - нету.
Поэтому выводиться будут числа за массивом (мусор) пока в памяти не встретится 0.
Либо замени условие цикла, к примеру на

while(i<sizeof(narr)/sizeof(narr[0]))

Либо просто добавь в конец массива 0:

int narr[] = { -1, 1, -2, 2, -4, 4, -8, 8, -16, 16, -64, 64, -128, 128, -32767, 32767, 0 }, i = 0, j = 1, num;

Сообщение отредактировано: cppasm - 12.02.11, 12:14

Спасибо большое! Я думал, что для числовых массивов не нужно ставить завершающий ноль. А если в массив должно входить число 0? Тогда только с помощью while? Век живи, век учись. Неисперпаемый язык С/C++!!!

не знаю на сколько это гууд, но можно сделать например так

    int a1[] = {0, 1, 2, 3, 4};
    int *a2[] = {&a1[0], &a1[1], &a1[2], &a1[3], NULL};
    int i = 0;
    while(a2[i])
    {
        printf("%d", *(a2[i]));
        ++i;
    }

tumanovalex, причём тут язык? Ты сам написал такую логику - цикл останавливается по достижению нуля. Смени условие выхода, и нуль в конце будет не нужен.

Да, похоже с годами я становлюсь только старше. Сам же сделал while(narr[i]), т.е. пока истинно, то выполнять. Еще раз проанализировал код cppasm:

  for(i=0; i<len; i++) {
    number<<=1;
    if(sbit[i] == '1') number |= 1;
  }

только пожалуй сейчас понял его нюансы. Очень хороший код. Интересно, это он сам придумал или этот код есть в какой-нибудь книге?

Цитата tumanovalex @ 12.02.11, 20:12

Интересно, это он сам придумал или этот код есть в какой-нибудь книге?

Это азы, известные любому, знакомому с битовой арифметикой.

Понятно, мне нужно побольше читать и практиковаться.

Знаковое десятичное в двоичное:

//--------------------------------
#include <bitset>
#include <string>
//--------------------------------
 string mystring;
 bitset <32> bs;
 bs = IntTostdBitSet("-1607");
 mystring = bitstring.to_string<char, char_traits<char>, allocator<char> >();
//--------------------------------
bitset<32> IntTostdBitSet(int dnum)
{
 int bitpos = 0, absdnum = abs(dnum);
 bitset <32> bs, bsone;
 
 bsone.set(0);
 //основной код
 while(absdnum > 0)
 {
  bs[(bitpos++)] = absdnum % 2;
  absdnum = absdnum/2;
 }
 //обратный и дополнительный код
 if(dnum < 0)
 {
  //обратный код
  bs.flip();
  //дополнительный код
  bs = bs | bsone;
 }
 return bs;
}