Дата  Запланированые курсы
30.07 Рисование на компьютере при помощи планшета (базовый курс)
30.07 Adobe After Effects. Создание анимации и эффектов
13.08 Средства векторной графики. Adobe Illustrator
27.08 Поисковая оптимизация (SEO)
03.09 Введение в тестирование программного обеспечения
10.09 DEV-J-MP+. Расширенная комплексная программа "Разработчик прикладного программного обеспечения (Язык Java)"
10.09 DEV-J10. Программирование на платформе Java. Введение в язык Java
10.09 MOC-20740B. Установка, Хранение и Вычисления с Windows Server 2016
10.09 Поисковая оптимизация (SEO) для профессионалов
10.09 DEV-J-CP. Комплексная программа "Разработчик прикладного программного обеспечения (Язык Java)"
10.09 Поисковая оптимизация (SEO) для профессионалов
10.09 Компьютерное проектирование в системе AutoCAD (базовый курс)
10.09 MOC-10985. Введение в базы данных SQL
10.09 Основы создания веб-сайтов. Adobe Dreamweaver
10.09 DEV-C22. Стандарт С++11, С++14, С++17 для прикладного программирования
17.09 MOC-20761. Создание запросов данных при помощи Transact-SQL
17.09 DEV-J20. Программирование на платформе Java. Стандартные пакеты
17.09 Средства растровой графики. Adobe Photoshop
24.09 DEV-J30. Программирование на платформе Java. Разработка многоуровневых приложений
24.09 MOC-20741B. Сетевая инфраструктура на основе Windows Server 2016
01.10 MOC-20762. Разработка баз данных SQL
01.10 Компьютерное проектирование в системе AutoCAD (базовый курс)
01.10 Профессиональная верстка сайтов. HTML5 и CSS3
01.10 DEV-С-CP+. Расширенная комплексная программа «Разработчик прикладного программного обеспечения (Языки С и C++)»
01.10 DEV-C10. Процедурное программирование. Языки С/C++
01.10 Основы алгоритмизации и программирования (Группа I)
01.10 Основы алгоритмизации и программирования (Группа II)
02.10 DEV-J-MP+. Расширенная комплексная программа "Разработчик прикладного программного обеспечения (Язык Java)"
02.10 DEV-J10. Программирование на платформе Java. Введение в язык Java
08.10 MOC-20764. Администрирование инфраструктуры баз данных SQL
08.10 MOC-20742B. Инфраструктура идентификации на основе Windows Server 2016
08.10 DEV-J60. Технологии разработки корпоративных приложений на платформе Java Enterprise Edition (Java EE)
08.10 Введение в тестирование программного обеспечения
08.10 QA-QAAB. Автоматизация тестирования ПО (Базовый курс)
15.10 Компьютерное проектирование в системе AutoCAD (профессиональный курс)
15.10 Средства векторной графики. Adobe Illustrator
15.10 DEV-OCPJP. Подготовка к сдаче сертификационных экзаменов серии Oracle Certified Professional Java Programmer
22.10 MOC-20744A. Безопасность инфраструктуры средствами Windows Server 2016
22.10 Введение в тестирование программного обеспечения
22.10 MOC-10987. Настройка производительности и оптимизация баз данных SQL
22.10 Основы создания веб-сайтов. Adobe Dreamweaver
24.10 NET-DLINKSW-LAB. Технологии коммутации современных сетей Ethernet. Лабораторный практикум
25.10 DEV-J20. Программирование на платформе Java. Стандартные пакеты
29.10 MOC-10961B. Автоматизация администрирования с Windows PowerShell
07.11 DEV-C20. Объектно-ориентированное программирование. Базовый уровень. Язык С++
12.11 Профессиональная верстка сайтов. HTML5 и CSS3
12.11 Компьютерное проектирование в системе AutoCAD (базовый курс)
19.11 DEV-J30. Программирование на платформе Java. Разработка многоуровневых приложений
26.11 Средства растровой графики. Adobe Photoshop
26.11 Поисковая оптимизация (SEO)
03.12 Компьютерное проектирование в системе AutoCAD (базовый курс)
03.12 DEV-C21. Объектно-ориентированное программирование. Углубленное изучение. Язык С++
10.12 Основы создания веб-сайтов. Adobe Dreamweaver
10.12 Поисковая оптимизация (SEO) для профессионалов
10.12 Средства векторной графики. Adobe Illustrator
17.12 Компьютерное проектирование в системе AutoCAD (профессиональный курс)
09.01 DEV-C22. Стандарт С++11, С++14, С++17 для прикладного программирования
14.01 DEV-OCPJP. Подготовка к сдаче сертификационных экзаменов серии Oracle Certified Professional Java Programmer
04.02 DEV-QT10. Прикладное программирование на С++ с использованием Qt. Базовый уровень
11.02 DEV-J60. Технологии разработки корпоративных приложений на платформе Java Enterprise Edition (Java EE)
11.03 Введение в тестирование программного обеспечения
11.03 Введение в тестирование программного обеспечения
Открыт набор на осенний семестр в Академию информатики для школьников Открыт набор на осенний семестр на программы второго высшего образования
Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error

Двоичная арифметика
Zem
#1 Оставлено : 24 февраля 2013 г. 18:11:29(UTC)
Ранг: Активный Участник

Группы: Зарегистрированные пользователи
Зарегистрирован: 23.08.2008(UTC)
Сообщений: 52
Баллов: 156
Мужчина

Сказал «Спасибо»: 4 раз
Имеется Си-стринг: "0F00 0000 0000 0000 0000 0000" (без пробелов).
Имеется область памяти: unsigned int m[3];, sizeof(unsigned int) == 4байт.

Каким образом построить в этой области памяти число, двоичная структура которого была бы одновременно, двоичным представлением числа изображенного на Си-стринге в 16-ричной форме?

Иными словами бинаризировать стринг так, чтоб printf("%X",m[0]); вывело:F000000 (6 нулей).

Заранее спасибо!
Реклама
М. Полубенцева
#2 Оставлено : 28 февраля 2013 г. 12:54:26(UTC)
Ранг: Новичок

Группы: Зарегистрированные пользователи
Зарегистрирован: 28.02.2013(UTC)
Сообщений: 8
Баллов: 24

Поблагодарили: 3 раз в 3 постах
Как то так: (не оптимизировала)
char* p = "0F0000000000000000000000";
unsigned int m[3]={0};
char tmp[] ={"0123456789ABCDEF"};
size_t n = strlen(p);
char* p1 = p;
for(int i=0; i<n;i++)
{
for(int j=0; j<sizeof(int) *2; j++)
{
int k=0;
for(; k<sizeof(tmp)-1; k++)
{
if(tmp[k]==*p1) break;
}
m[i] = (m[i]<<4) | k;
p1++;
}

}

printf("%X", m[0]);
return 0;
1 пользователь поблагодарил М. Полубенцева за этот пост.
Zem оставлено 02.03.2013(UTC)
М. Полубенцева
#3 Оставлено : 28 февраля 2013 г. 15:41:00(UTC)
Ранг: Новичок

Группы: Зарегистрированные пользователи
Зарегистрирован: 28.02.2013(UTC)
Сообщений: 8
Баллов: 24

Поблагодарили: 3 раз в 3 постах
Пожалуй, вот вариант получше

char* p = "0F1a00000000000000000000";
unsigned int m[3]={0};

size_t n = strlen(p);
char* p1 = p;
for(int i=0; i<n;i++)
{
for(int j=0; j<sizeof(int) *2; j++)
{

int k;
if(*p1>='0' && *p1<='9')
{
k = *p1 - '0';
}else
{
k=(*p1|0x20) - 'a' + 10;

}


m[i] = (m[i]<<4) | k;
p1++;
}

}

printf("%X", m[0]); return 0;
Zem
#4 Оставлено : 2 марта 2013 г. 17:09:54(UTC)
Ранг: Активный Участник

Группы: Зарегистрированные пользователи
Зарегистрирован: 23.08.2008(UTC)
Сообщений: 52
Баллов: 156
Мужчина

Сказал «Спасибо»: 4 раз
Два варианта это здорово!
Наверно всё таки size_t n = 3;, я прав?
А по поводу k=(*p1|0x20) - 'a' + 10; непонятно, хотелось бы поподробнее.
Zem
#6 Оставлено : 2 марта 2013 г. 17:10:48(UTC)
Ранг: Активный Участник

Группы: Зарегистрированные пользователи
Зарегистрирован: 23.08.2008(UTC)
Сообщений: 52
Баллов: 156
Мужчина

Сказал «Спасибо»: 4 раз
О ужас!
Я так увлёкся формулировкой вопроса, что задал не тот вопрос.
Ну да ладно, можно считать этот вопрос вводным.

А теперь самое сложное.

Как Си-стринг "0900 0000 0000 0000 0000 0000" (без пробелов) в 10-чной форме бинаризировать(загрузить в unsigned int m[3];) так, чтоб printf("%X",m[0]); вывело:130e?

То есть: 900 0000 0000 0000 0000 0000 decimal => 130e e8e7 1790 4440 0000 hexadecimal

printf("%X",m[1]); => e8e71790
printf("%X",m[2]); => 4440 0000
М. Полубенцева
#5 Оставлено : 2 марта 2013 г. 21:22:30(UTC)
Ранг: Новичок

Группы: Зарегистрированные пользователи
Зарегистрирован: 28.02.2013(UTC)
Сообщений: 8
Баллов: 24

Поблагодарили: 3 раз в 3 постах
Автор: Zem Перейти к цитате
Два варианта это здорово!
Наверно всё таки size_t n = 3;, я прав?
А по поводу k=(*p1|0x20) - 'a' + 10; непонятно, хотелось бы поподробнее.

Нет, Вы не правы...
"n" - это количество символов в строке. В цикле нужно "перебрать" все символы

Расшифровываю k=(*p1|0x20) - 'a' + 10;

*p1|0x20 - шестнадцатеричные цифры a,b,c,d,e,f A,B,C,D,E,F можно задавать как в верхнем, так и в нижнем регистре. Коды различаются одним разрядом (0x20). (*p1|0x20) - это перевод в нижний регистр (чтобы не писать два выражения).

(*p1|0x20) - 'a' - получаю значения 0, 1, 2, 3, 4, 5 в зависимости от кода символа

(*p1|0x20) -'a' + 10 - получаю 10, 11, 12, 13, 14, 15
1 пользователь поблагодарил М. Полубенцева за этот пост.
Zem оставлено 02.03.2013(UTC)
М. Полубенцева
#7 Оставлено : 10 марта 2013 г. 17:04:47(UTC)
Ранг: Новичок

Группы: Зарегистрированные пользователи
Зарегистрирован: 28.02.2013(UTC)
Сообщений: 8
Баллов: 24

Поблагодарили: 3 раз в 3 постах
Думаю, что Вы не совсем правильно написали, что должно быть выведено. И не очень понятно: в заданной строке левая цифра должна быть самой старшей?

//Сложение двух целых произвольной (с точностью до байта) длины "n"
//Результат - обратно в p1
void Sum(unsigned char* p1, unsigned char* p2, size_t n)
{
unsigned char perenos=0;
for(size_t i=0; i<n; i++)
{
unsigned short s = (*p1)+(*p2) + perenos;
*p1 = static_cast<unsigned char>(s);
perenos = static_cast<unsigned char>(s>>8);
p1++;
p2++;

}
}

//Умножение целого произвольной длины ("n" байтов) на значение, которое помещается в байт (v)
void mul(unsigned char* p, unsigned char* res, size_t n, unsigned char v)
{
unsigned char perenos=0;
for(size_t i=0; i<n; i++)
{
unsigned short s = (*p)*v + perenos;
*res = static_cast<unsigned char>(s);
perenos = static_cast<unsigned char>(s>>8);
//if(perenos==0) break;
p++;
res++;

}
}
int _tmain(int argc, _TCHAR* argv[])
{

char* p = "123456789123456789";//"090000000000000000000000";
unsigned int m[4]={0};//здесь результат
unsigned char pow10[sizeof(m)*sizeof(int)]={1};//здесь копим 10 в степени
size_t n = strlen(p);

char* p1 = p+n; //направляем на завершающий ноль (признак конца строки)
for(int i=0; i<n; i++)
{
--p1;
//очередной символ переводим в значение
unsigned char val = *p1 - '0';
// умножаем val на 10 в соответствующей степени
unsigned char a[sizeof(m)*sizeof(int)] = {0};
mul(pow10,a,sizeof(m)*sizeof(int),val);


//и складываем с уже накопленным результатом
Sum(reinterpret_cast<unsigned char*>(m),a,n-1);


//Копим степень 10
mul(pow10,pow10,3*sizeof(int),10);

__asm nop
}


printf("%x\n",m[0]);
printf("%x\n",m[1]);
printf("%x\n\n\n",m[2]);
}
1 пользователь поблагодарил М. Полубенцева за этот пост.
Zem оставлено 10.03.2013(UTC)
Zem
#8 Оставлено : 10 марта 2013 г. 21:15:05(UTC)
Ранг: Активный Участник

Группы: Зарегистрированные пользователи
Зарегистрирован: 23.08.2008(UTC)
Сообщений: 52
Баллов: 156
Мужчина

Сказал «Спасибо»: 4 раз
В заданной строке левая цифра должна быть самой старшей.

Тоесть Си-стринг "090000000000000000000000" есть число:
90 000 000 000 000 000 000 000 == девять на десять в 22-й степени.
Система десятичная.

Кто ответит, чему равно 16-ричное представление этого числа?
М. Полубенцева
#9 Оставлено : 10 марта 2013 г. 21:19:46(UTC)
Ранг: Новичок

Группы: Зарегистрированные пользователи
Зарегистрирован: 28.02.2013(UTC)
Сообщений: 8
Баллов: 24

Поблагодарили: 3 раз в 3 постах
Вроде проверила - все правильно. Только распечатайте в hex-е
Успехов!
Zem
#10 Оставлено : 10 марта 2013 г. 22:08:20(UTC)
Ранг: Активный Участник

Группы: Зарегистрированные пользователи
Зарегистрирован: 23.08.2008(UTC)
Сообщений: 52
Баллов: 156
Мужчина

Сказал «Спасибо»: 4 раз
Автор: М. Полубенцева Перейти к цитате
Код:
//Сложение двух целых произвольной (с точностью до байта) длины "n"
//Результат - обратно в p1
void Sum(unsigned char* p1, unsigned char* p2, size_t n)
{
    unsigned char perenos=0;
    for(size_t i=0; i<n; i++)
    {
        unsigned short s = (*p1)+(*p2) + perenos;
        *p1 = static_cast<unsigned char>(s);
        perenos = static_cast<unsigned char>(s>>8);
        p1++;
        p2++;
        
    }
}

//Умножение целого произвольной длины ("n" байтов) на значение, которое помещается в байт (v)
void mul(unsigned char* p, unsigned char* res, size_t n, unsigned char v)
{
    unsigned char perenos=0;
    for(size_t i=0; i<n; i++)
    {
        unsigned short s = (*p)*v + perenos;
        *res = static_cast<unsigned char>(s);
        perenos = static_cast<unsigned char>(s>>8);
        //if(perenos==0) break;
        p++;
        res++;
        
    }
}
int _tmain(int argc, _TCHAR* argv[])
{

        char* p = "123456789123456789";//"090000000000000000000000";
        unsigned int m[4]={0};//здесь результат
        unsigned char pow10[sizeof(m)*sizeof(int)]={1};//здесь копим 10 в степени
        size_t n = strlen(p);

        char* p1 = p+n; //направляем на завершающий ноль (признак конца строки)
        for(int i=0; i<n; i++)
        {
                --p1;
                //очередной символ переводим в значение
                unsigned char val = *p1 - '0';
                // умножаем val на 10 в соответствующей степени
                unsigned char a[sizeof(m)*sizeof(int)] = {0};
                mul(pow10,a,sizeof(m)*sizeof(int),val);
                

                //и складываем с уже накопленным результатом
                Sum(reinterpret_cast<unsigned char*>(m),a,n-1);
                
                                
                //Копим степень 10
                mul(pow10,pow10,3*sizeof(int),10);

                __asm nop
            }

        
     printf("%x\n",m[0]);
        printf("%x\n",m[1]);
        printf("%x\n\n\n",m[2]);
}


Отлично!
Это то, чего я хотел!
Ну, а порядок следования интов всегда можна поменять, проблемма не в этом.
К сожалению мой алгоритм "загрузки" стринга имеет тот же порядок вычислительной сложности.
Неужели нет более эффективных алгоритмов?
М. Полубенцева
#11 Оставлено : 11 марта 2013 г. 10:44:37(UTC)
Ранг: Новичок

Группы: Зарегистрированные пользователи
Зарегистрирован: 28.02.2013(UTC)
Сообщений: 8
Баллов: 24

Поблагодарили: 3 раз в 3 постах
Возможно, можно чуть повысить эффективность за счет:
x*10 == x*2 + x*8 == x<<1 + x<<3

Мой пример "не вылизан". На самом деле нужно сделать что-нибудь:
class MyLongInt{
unsigned char* m_p; //указатель на двоичное представление длинного целого любой
(с кратностью до байта) размерности
size_t m_n; //количество байтов в динамическом массиве
public:
MyLongInt(const char*);
MyLongInt operator+ (const MyLongInt&) const;
MyLongInt& operator*= (const MyLongInt&) ;
~MyLongInt();
и т.д.
};
Zem
#12 Оставлено : 11 марта 2013 г. 19:19:21(UTC)
Ранг: Активный Участник

Группы: Зарегистрированные пользователи
Зарегистрирован: 23.08.2008(UTC)
Сообщений: 52
Баллов: 156
Мужчина

Сказал «Спасибо»: 4 раз
Саму арифметику больших чисел я уже написал.

Меня удивило на сколько затратно преобразование из десятичной системы по сравнению с преобразованием из 16-ричной.

Мой алгоритм (конструктор принимающий 10-чный стд-стринг):
Код:

    Int(string s)
    {
        Int sum = 0;
        char cstr[2] = {'\0', '\0'};
        for (unsigned int i = 0; i < s.size(); ++i)
        {
            cstr[0] = s[i];
            sum *= 10;
            sum += Int(atoi(cstr));
        }
        *this = sum;
    }

по сути равен Вашему алгоритму:


Код:
int _tmain(int argc, _TCHAR* argv[])
{
        char* p = "090000000000000000000000";
        unsigned int m[4]={0};
        unsigned char pow10[sizeof(m)*sizeof(int)]={1};
        size_t n = strlen(p);

        char* p1 = p+n;
        for(int i=0; i<n; i++)
        {
                --p1;
                unsigned char val = *p1 - '0';
                unsigned char a[sizeof(m)*sizeof(int)] = {0};
                mul(pow10,a,sizeof(m)*sizeof(int),val);

                Sum(reinterpret_cast<unsigned char*>(m),a,n-1);

                mul(pow10,pow10,3*sizeof(int),10);

                __asm nop
        }

        printf("%x\n",m[0]);
        printf("%x\n",m[1]);
        printf("%x\n\n\n",m[2]);
}

тоесть "большое число" точно так же формируется путём умножения на десять и накопления при каждой итерации.

Получается, что существенно другого алгоритма не существует...
М. Полубенцева
#13 Оставлено : 13 марта 2013 г. 21:55:13(UTC)
Ранг: Новичок

Группы: Зарегистрированные пользователи
Зарегистрирован: 28.02.2013(UTC)
Сообщений: 8
Баллов: 24

Поблагодарили: 3 раз в 3 постах
Кое-что в приведенном фрагменте мне показалось странным. Не могли бы Вы привести Ваш класс целиком
Zem
#14 Оставлено : 13 марта 2013 г. 23:26:05(UTC)
Ранг: Активный Участник

Группы: Зарегистрированные пользователи
Зарегистрирован: 23.08.2008(UTC)
Сообщений: 52
Баллов: 156
Мужчина

Сказал «Спасибо»: 4 раз
Вполне возможно, что до меня арифметику НА СТОЛЬКО больших чисел ещё никто не писал. Потому подарить новинку могу только после приёма меня на работу. Я уже давно ищу работу где б ценили людей способных изобритать и творить прочие инновации.

Если есть конкретные вопросы, задавайте. Желающим протестировать возможности класса могу выслать на E-mail консольный вариант калькулятора работающего на моей арифметике.
М. Полубенцева
#15 Оставлено : 14 марта 2013 г. 12:09:25(UTC)
Ранг: Новичок

Группы: Зарегистрированные пользователи
Зарегистрирован: 28.02.2013(UTC)
Сообщений: 8
Баллов: 24

Поблагодарили: 3 раз в 3 постах
Хочу вас огорчить - такие задачки я даю своим студентам в качестве курсовика после первого семестра...
А Вам хотела подсказать как лучше, но теперь удаляюсь...
Желаю удачи!
Zem
#16 Оставлено : 16 марта 2013 г. 1:28:52(UTC)
Ранг: Активный Участник

Группы: Зарегистрированные пользователи
Зарегистрирован: 23.08.2008(UTC)
Сообщений: 52
Баллов: 156
Мужчина

Сказал «Спасибо»: 4 раз
Задачка: реализовать арифметику больших чисел (класс Int).
Условие: длина числа задаётся длинной стринга, число может состоять из миллионов десятичных цифр.

У меня ушла неделя.
RSS Лента  Atom Лента
Пользователи, просматривающие эту тему
Guest (3)
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.