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

Как определить сколько единиц в двоичном коде символа? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.60
Виктор Яловой
0 / 0 / 0
Регистрация: 19.12.2013
Сообщений: 15
19.12.2013, 03:06     Как определить сколько единиц в двоичном коде символа? #1
как определить сколько единиц в двоичном коде символа? (С\С++)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2013, 03:06     Как определить сколько единиц в двоичном коде символа?
Посмотрите здесь:

C++ сколько единиц содержится в двоичном представлении переменной типа char
C++ Написать программу на языке С, которая рекурсивно вычисляет количество единиц в двоичном коде заданного пользователем натурального числа
C++ Подсчёт единиц и нулей в двоичном коде
C++ Как содержимое файла *.txt переписать в двоичном коде в другой файл?
Определить, каких цифр больше в двоичном представлении натурального числа N – нулей или единиц C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
19.12.2013, 03:20     Как определить сколько единиц в двоичном коде символа? #2
Puzzle: Fast Bit Counting
Виктор Яловой
0 / 0 / 0
Регистрация: 19.12.2013
Сообщений: 15
19.12.2013, 03:28  [ТС]     Как определить сколько единиц в двоичном коде символа? #3
ничего не понятно
есть работающий код, который показывает сколько единиц в двоичном коде символа, которого мы вводим??
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
19.12.2013, 03:49     Как определить сколько единиц в двоичном коде символа? #4
вот придумал вам идиальное решение (с точки зрения алгоритмической сложности лучше не придумать - сложность О(количество единиц в бинарном представлении числа)), вряд ли это возможно сделать с меньшей сложностью
C++
1
2
3
4
5
6
std::size_t F(unsigned long long n)
{
    std::size_t i(0);
    for (;n;++i) n&=n-1;
    return i;
}
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
19.12.2013, 03:57     Как определить сколько единиц в двоичном коде символа? #5
Цитата Сообщение от Виктор Яловой Посмотреть сообщение
ничего не понятно
есть работающий код
Там всё работающее, на выбор, с пояснениями и замерами.
Виктор Яловой
0 / 0 / 0
Регистрация: 19.12.2013
Сообщений: 15
19.12.2013, 04:06  [ТС]     Как определить сколько единиц в двоичном коде символа? #6
Цитата Сообщение от abit Посмотреть сообщение
вот придумал вам идиальное решение (с точки зрения алгоритмической сложности лучше не придумать - сложность О(количество единиц в бинарном представлении числа)), вряд ли это возможно сделать с меньшей сложностью
C++
1
2
3
4
5
6
std::size_t F(unsigned long long n)
{
    std::size_t i(0);
    for (;n;++i) n&=n-1;
    return i;
}
Я конечно извиняюсь, но я знаком только с С, С++ только начал изучать.
Можно ли построчно объяснить этот код?
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
19.12.2013, 04:11     Как определить сколько единиц в двоичном коде символа? #7
Цитата Сообщение от abit Посмотреть сообщение
вряд ли это возможно сделать с меньшей сложностью
Если обменять память на быстродействие (для char/short), то с использованием Look-up table - за O(1).
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
19.12.2013, 04:21     Как определить сколько единиц в двоичном коде символа? #8
Цитата Сообщение от Виктор Яловой Посмотреть сообщение
Я конечно извиняюсь, но я знаком только с С, С++ только начал изучать.
Можно ли построчно объяснить этот код?
конечно можно, не вопрос) учите C++
давайте разберём код
первая строчка - std::size_t F(unsigned long long n)
объявляем функцию F, которая возвращает некое значение типа std::size_t (почитайте про него сами, суть - тип, который позволяет возвращать количество чего-то, допустимый в нашей системе, в нашем случае количество единичных бит в битовом представлении числа)
unsigned long long - наиболее длинный тип о котором мне известно под различными платформами, где имеет смысл говорить о битовом представлении, конечно в знаковых тоже имеет смысл говорить, но это совсем другая история

вторая строчка - std::size_t i(0);
тут всё ясно - инициализируем переменную, которую потом возвратим в ответ на вызов F, вызываем конструктор, чтобы её обнулить (на всякий случай, реально - тут это не надо, ибо конструктор по умолчанию обнулит)

третья строчка - for (;n;++i) n&=n-1;
ну это сама суть происходящего, разберите на досуге
если раскрыть в псевдокод (а точнее в паскаль) то будет что-то типа такого:
Delphi
1
2
3
4
5
while(n<>0) do
begin
  n:=n AND (n-1);
  inc(i);
end;
в общем это суть моей идеи) разберитесь и всё будет ясно
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
19.12.2013, 04:28     Как определить сколько единиц в двоичном коде символа? #9
Цитата Сообщение от abit Посмотреть сообщение
суть моей идеи
#2 по ссылке выше. Там же и пояснение. :-)
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
19.12.2013, 04:49     Как определить сколько единиц в двоичном коде символа? #10
Цитата Сообщение от gazlan Посмотреть сообщение
#2 по ссылке выше. Там же и пояснение. :-)
да и правда) но извините, я это сам придумал вот совсем недавно и давайте сравним мой код:

C++
1
2
3
4
5
6
std::size_t F(unsigned long long n)
{
    std::size_t i(0);
    for (;n;++i) n&=n-1;
    return i;
}
и непонятно чей по вашей ссылке:
C++
1
2
3
4
5
6
7
8
int bitcount (unsigned int n)  {
   int count = 0 ;
   while (n)  {
      count++ ;
      n &amp;= (n - 1) ;
   }
   return count ;
}
на лицо:
1) мой код компактнее
2) мой код в 4 раза больше имеет область определения функции, просто сравните std::size_t и int или unsigned long long и unsigned int
3) мой код опять же не требует знаковости количества единичных бит, вот как понимать "int count = 0 ; " ??? count может быть отрицательным? отрезают половину значений фиг знает на что
4) сам цикл while в том коде увеличивает время выполнения, дизассеблируйте и сравните
5) что ещё за "&amp;" это даже не скомпилируется, в отличии от моего кода, объясните новичкам что такое "&amp;"
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
19.12.2013, 05:32     Как определить сколько единиц в двоичном коде символа? #11
Цитата Сообщение от abit Посмотреть сообщение
я это сам придумал вот совсем недавно
И это только плюс вам.

и непонятно чей
Я думаю, он столько раз переизобретался, что изначального автора уже не найти.

в 4 раза больше имеет область определения
Это как раз непринципиально - можете подставить любой целый тип, доступный на вашей машине.

не требует знаковости
Сам "входной" параметр - беззнаковый: unsigned int n, а тип счетчика безразличен - для 64 бит хватит даже signed char

сам цикл while в том коде увеличивает время выполнения
Это может зависеть от опций оптимизации. Не думаю, что на самом деле там будет разница в коде. У меня (MSVC/DEBUG) они выглядят, практически, неразличимо.

Цитата Сообщение от abit Посмотреть сообщение
что ещё за "&amp;"
Это издержки HTML. На самом деле, там '&', и если вы скачаете С-файл по ссылке вверху странички, то там все в порядке.
Миниатюры
Как определить сколько единиц в двоичном коде символа?  
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
19.12.2013, 06:03     Как определить сколько единиц в двоичном коде символа? #12
Цитата Сообщение от gazlan Посмотреть сообщение
можете подставить любой целый тип, доступный на вашей машине.
так не бывает, ну может где-то бывает, но обычно не имеет смысла писать под конкретную машину, обычно пишут под всё вероятные платформы и от сюда дальнейшие проблемы:

Сам "входной" параметр - беззнаковый: unsigned int n, а тип счетчика безразличен - для 64 бит хватит даже signed char
про первую часть предложения - речь то шла не о входном параметре а о возвращаемом значении функции, он почему-то знаковый, неизвестно зачем - отрезали половину определения функции,
про вторую часть предложения - я согласен, хватит char, но кто знает, я пережил несколько трагичных моментов смены int с 16-бит на 32 и на 64 бита, казалось бы базовый тип, но вот так бывает... в то же время писал недавно под SAM7 и int там был всё тот же 16-бит, я себе памятку сделал для C++ с базовыми типами, которые одинаковы везде и остальные вывожу через них всегда, а все структуры и классы всегда с атрибутом пакед стараюсь делать
MSVC/DEBUG
Поглядел на Вашу картинку с ассемблерным кодом - в общем VS видимо иначе мыслит чем мой gcc, сложно сравнить, потому что VS бред выдаёт реальный, ну что такое скажем add eax,1 ? почему не inc eax? это сэкономит кучу тактов и не будет грузить конвеер, аналогично sub ecx,1 - бред, да и три следующие строчки любопытная шизофазия, в общем даже обсуждать не хочется

Это издержки HTML. На самом деле, там '&'
да это понятно, просто потроллил ваш совет - как новичкам разобрать сие иероглифы)
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
19.12.2013, 14:08     Как определить сколько единиц в двоичном коде символа? #13
В целом согласен с вами, единственное замечание:

Цитата Сообщение от abit Посмотреть сообщение
VS бред выдаёт реальный
Вы не обратили внимания на пометку "DEBUG". Генерация кода существенно зависит от опций оптимизации (и, к слову, иногда это приводит к серьезным проблемам при отладке). Вот тот же цикл for в Release:
Миниатюры
Как определить сколько единиц в двоичном коде символа?  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.12.2013, 14:42     Как определить сколько единиц в двоичном коде символа?
Еще ссылки по теме:

Напишите программу, которая определяет, сколько единиц содержится в двоичном представлении переменной типа char C++
C++ Как представить int в двоичном коде
Определить в двоичном представлении числа максимальное количество расположенных рядом единиц C++

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

Или воспользуйтесь поиском по форуму:
gromo
 Аватар для gromo
366 / 265 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
19.12.2013, 14:42     Как определить сколько единиц в двоичном коде символа? #14
Цитата Сообщение от abit Посмотреть сообщение
вторая строчка - std::size_t i(0);
тут всё ясно - инициализируем переменную, которую потом возвратим в ответ на вызов F, вызываем конструктор, чтобы её обнулить (на всякий случай, реально - тут это не надо, ибо конструктор по умолчанию обнулит)
i - автоматическая переменная, для нее не гарантируется обнуление, в отличии от глобальных.
Yandex
Объявления
19.12.2013, 14:42     Как определить сколько единиц в двоичном коде символа?
Ответ Создать тему
Опции темы

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