Есть число от 0 до 255. Соответственно влезает в один байт. Надо узнать сколько в нем выставлено битов. Мысли есть?

8???

8

преобразовать в двоичное и посчитать "1"?

По високосным и до 9 доходит.

(1) Да нет. Есть определенное значение байта, надо узнать сколько бит для данного байта установлено.

(4) ну эт редко

(3) А как в двоичное преобразовать?

(5) задай вопрос по-другому

(5) где установлено?

телепатирую, что нужно посчитать количество одоек в строке типа "01100100"

(8) Возьмем число 1. Это в двоичном представлении 1, т.е. выставлен один бит. Число 2 в двоичном представлении равно 10, тоже один бит выставленным получается.

(7) функцией...

дес - дв
0 - 00
1 - 01
2 - 10
3 - 11
4 - 100
...

(5) сколько единичных (ненулевых) бит в нем?

(10) У меня на входе Число на входе, а не строка

(14) Угу

(12) Понятно ) Но мне алгоритм интересен

Забыл сказать. Это должно работать быстро, т.к. такая функция будет вызываться очень много раз.

Блин, почему в 1С нету битовых операций? (

(18)  кури XOR  в Math

Перем Массив[256];

Функция Сдвиг(а,н,куда)
   Перем Ат;
   Скрипт=СоздатьОбъект("MSScriptControl.ScriptControl");
   Скрипт.language="javascript";
   Математика=Скрипт.Eval("Math");
   Если а=0 Тогда
       Возврат 0;
   Иначе
       Ат=Математика.pow(2,Цел(Лог(а)/Лог(2)))+1
   КонецЕсли;
   Если Ат<65535 Тогда
       Ат=65535;
   КонецЕсли;
   Если куда=1 Тогда
       Возврат а/Математика.pow(2,н);
   Иначе
       Возврат а*Математика.pow(2,н)%Ат;
   КонецЕсли;
КонецФункции

Функция Расчет(Знач НачСумма,Сп)
   Скрипт=СоздатьОбъект("MSScriptControl.ScriptControl");
   Скрипт.language="vbscript";
   Для к=1 По Сп.РазмерСписка() Цикл
       НачСумма=Массив[Скрипт.Eval("("+Сдвиг(НачСумма,8,1) +" AND 255) XOR "+Сдвиг(НачСумма,8,0)+" XOR "+Сдвиг(НачСумма,8,0)+" XOR "+Сп.ПолучитьЗначение(к))+1];
       НачСумма=Скрипт.Eval(НачСумма+" AND 65535");
   КонецЦикла;
   Возврат НачСумма;
КонецФункции

Когда то на ВБ упаковывал 16 флажков в одно число. Все было настолько просто... помню, что в 7.7 такого функционала не было, в 8 тоже не нашли и забросили это дело. Упаковка через исключающее "или" и распаковка через "и" битовых операциях (или наоборот)

(17)
Функция ДесВДвоич(ТекЧисло)
  Если ТекЧисло = 0 Тогда
     Возврат "0";
  ИначеЕсли ТекЧисло = 1 Тогда
     Возврат "1";
  ИначеЕсли ТекЧисло = 2 Тогда
     Возврат "10";
  ИначеЕсли ТекЧисло = 3 Тогда
     Возврат "11";
     ...ну ты понел )... и так далее
  КонецЕсли;
КонецФункции

(20) Не вкурил. И как мне получить число битов для моего числа?

(22) Мне не десятичное представление нужно, а количество единичек в числе

Единиц=0;
Для сч=1 По 8 Цикл
Если Нечет(ВхЧисло)=1 Тогда
Единиц=Единиц+1;
КонецЕсли;
ВхЧисло=Цел(ВхЧисло/2);
КонецЦикла;

(24) Не бинарное представление, хотел сказать

(20) yahoo.eu

(25) Уже вариант. Но кажется, что будет медленно, функция сто тыщ миллионов будет вызываться.

Хрень какая то. Бит это не только 1 но и 0. Всегда 8 бит.

8 раз дели на 2 и при этом считай сумму остатка от деления

В 1С есть оператор % который дает остаток (хвостик) от деления.
Делить на два таким способом 8 раз и выводить на экран хвостик - получится двоичное число (начиная с младшей цифры). Тут можно и единицы посчитать, и само двоичное число получить.

Единиц=0;
Пока ВчЧисло>0 Цикл
Ост = ВчЧисло % 2;
Единиц=Единиц+Ост;
ВхЧисло=(ВхЧисло-Ост)/2;
КонецЦикла;

(28) Если нужно быстрее...
Если числа только с 0 до 255, то запомни где-нибудь табличку соответствия Число-Кол-во 1.

(33) Отлично! То что доктор прописал! Спасибо! )

То бишь у тебя получится таблица соответвия с колонками "Число" и "Количество единиц". Или еще лучше массив, где индекс элемента - это число, а значение массива - это кол-во единиц. Тогда тупо вызваешь Массив[15]:)

(23) учи матчасть

(35) Да, быстрее не придумаешь )

(35) стопудов! а заполнять при начале работы с помощью (32)

(37) Открой военную тайну, зачем тебе это вообще надо?

(28)
мат=СоздатьОбъект("Математика");
Единиц=мат.bitand(арг,128)/128+мат.bitand(арг,64)/64+
мат.bitand(арг,32)/32+
мат.bitand(арг,16)/16+
мат.bitand(арг,8)/8+мат.bitand(арг,4)/4+мат.bitand(арг,2)/2+мат.bitand(арг,1);

Вот, писал для семерки.
Как разложить в двоичный код:
Функция ВернутьДвКод(ч)
   х = Цел(ч/2);
   Если х>0 Тогда
       Возврат ВернутьДвКод(х)+Строка(ч-х*2);
   КонецЕсли;    
   Возврат Строка(ч-х*2);
КонецФункции    
//*******************************************

Процедура Сформировать()
  рез = ВернутьДвКод(ВыбЧисло);
  Сообщить(рез);
  Сообщить(Прав(Рез,1)) ;
КонецПроцедуры

(39) Есть одна специфическая задачка...

(42) которую конечно надо решить на 1Це

(43) Ну, разные проблемы бывают. Приходится решать. В УПП вон системы линейных уравнений решают и ничего...

(42) Блин, заинтриговал, раздраконил любопытство ...и свалил:)

(44) СЛУ еще понять можно и то я бы само решение вынес бы во внешнюю компоненту. Мне понятно зачем решать СЛУ в УПП, зачем битовые операции в учетных задачах - непонятно

Тупо делить число на 128, остаток от деления на 64 и т.д. Результаты(целые, ес-но) сложить.

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

(48) например права хранятся в байте и при устаноке надо контролировать, что нельзя более 5 галок одновременно ставить...

а вообще битовые операции в 1с - это нонсенс, так как в 1с НЕТУ битового типа, как и вообще числовового то-же нету (в нормальном понимании)

(45)(46)(48) Контроль четности например

(50) Для контроля четности достаточно контролировать один бит :-)

(51) +1. Младший.

Или последнюю цифру числа.

жеееесть...
(49) У тебя права в 1С в "байте" хранятся? Че курил то?

(54) ПОчему бы и нет?
У меня правила миграции документа в двух байтах :-))

(50) Контроль четности чего? Числа с 0 до 255? Тогда, если последнее число 0 или четное - тогда число четное. Только вот опять для чего?:) Еще и сто миллионов раз будет проверяться четность? Колитесь короче:)

(55) Тоже занимался подсчетом еденичек в двоичном предсавлении байта?

(57) "В отличие от" - я сначала думаю, а потом делаю... :-)

(50) Ааааа, какой-то алгоритм связанный с шифровкой-дешифровкой... криптографией занимаемся в 1С?:)

(59) Ну необязательно криптографией - может, контролем данных...

(54) я где-то говорил про права 1с??????

я говорил просто про ПРАВА, которые могуб быть например переданы в ХП совершенно другой учетной системы (например интернет магазина).

Я говорю, что ситуация возможна, но в рамках 1с абсурдна.

зы
всегда удивлялся как люди умеют искажать явно выраженое мнение...

(59) у меня например есть такой код в моей программе

           Знак = "";
           Пока Знак <> Неопределено Цикл
               Знак = Текст.Прочитать(1);
               Если Знак <> Неопределено Тогда
                   // декодируем символ
                   Если е = 36 Тогда
                       е = 1;
                   Иначе
                       е = е + 1;
                   КонецЕсли;
                   
                   ЗнакКлюча    = КодСимвола(ВолшебныйКлюч, е);
                   Знак        = КодСимвола(Знак);
                   // надо сделать следующую операцию
                   // Знак = Знак XOR ЗнакКлюча
                   РезЗнак = 0;
                   Для е1 = 1 по 8 Цикл
                       ИтоговыйБит = 1;
                       Маска=Pow(2, е1-1);
                       Бит1=Цел(Знак / Маска);
                       Бит2=Цел(ЗнакКлюча / Маска);
                       Если ((Бит1+Бит2)/2)=Окр((Бит1+Бит2)/2,0) Тогда
                           ИтоговыйБит = 0;
                       КонецЕсли;
                       РезЗнак = РезЗнак + Маска * ИтоговыйБит;
                   КонецЦикла;                
                   
                   // все, теперь добавим к уже расшифрованной строке
                   СтрокаФайла = СтрокаФайла + Символ(РезЗнак);                
               КонецЕсли;
           КонецЦикла;

(61) Да, лан, че ты завелся :-)
(0) Ну, давай, колись быстро, что ваяешь :-)))

(0)
КолБит = 0;
Пока Байт > 0 Цикл
   КолБит = КолБит + Байт % 2;
   Байт = Цел(Байт/2);
КонецЦИкла;

хе

(64) Уже нашли самый простой и самый быстрый вариант )

(63) Сие тайна есть великая )

(59) Тепло... )

(65) Пример приведи

(65) Ну а этим будешь инициализировать свою табличку.

(68)

Перем БитыВБайте;

Функция КоличествоБит(Число)
 Возврат БитыВБайте[Число];
КонецФункции

БитыВБайте[0] = 0;
БитыВБайте[1] = 1;
БитыВБайте[2] = 1;
БитыВБайте[3] = 2;
...
БитыВБайте[255] = 8;

(64) Вариант в (32) симпатичней.

(70) Жесть

(72) То, что доктор прописал )

(72) Есть варианты быстрее?

(74) И проще )))

(74) На ассемблере

Поставьте плиз категорию "Юмор" ветке.

(76) Эта реализация похоже для любых языков самая быстрая

(73) Идея праильная ))) Только массив инициализируй перед вызовом своего криптоапи

(79) + в цикле

(73) Массив при загрузке модуля будет инициализироваться

(81) Т.е. ты всерьез будешь набивать 255 строк теста ? а если ошибешься где нить ?

(82) сгенерировать в екселе и поставить в 1с

(82) и не 255 строк, а 256 строк

(84) И на "0" - тоже? :-)

1 - 1 бит в конце
2 - 2 бит
4 - 3 бит
8 - 4 бит
16 - 5 бит
32 - 6 бит
64 - 7 бит
128 - 8 бит

разбивай число на составляющие..

>=128 - 8-й бит установлен
число-128>=64 7-й бит установлен
и т.д.

(86) что это?

(86) тормозной вариант, уже ведь обсудили.

(87) Чило назови от 0 до 255

(89) 0

Самый быстрый будет вот этот вариант:

Результат = 0;

е = 0;
Пока е <= 8 Цикл
е = е + 1;
Если Значение > СписокЗначений[е] Тогда
 Результат = Результат+1;
 е = е + 1;
 если е>8 тогда прервать конецесли;
ИначеЕсли Значение > СписокЗначений[е] Тогда
 Результат = Результат+1;
 е = е + 1;
 если е>8 тогда прервать конецесли;
ИначеЕсли Значение > СписокЗначений[е] Тогда
 Результат = Результат+1;
 е = е + 1;
 если е>8 тогда прервать конецесли;
.......  
КонецЕсли;
КонецЦикла;


список имеет значения 128,64,32 ....

Операции сравнения всегда работают быстрее арифметических

>128 0
>64 0
>32 0
>16 0
>8 0
>4 0
>2 0
>1 0

(91)+ есть ошибка, но где-то в этом направлении

(81) Один раз написать массив не проблема

(86), (91) - это нерабочие варианты

(95) ты проверь

(93) Самым быстрым будет
Если Арг=0 тогда 0 иначе БитВБайте[Арг]

(91) Быстрее чем "Возврат БитыВБайте[Число]"? ;)

(95) Вот рабочий

Результат = 0;
е = 0;
Пока е <= 8 Цикл
е = е + 1;
Если Значение > СписокЗначений[е] Тогда
 Результат = Результат+1;
 Значение = Значение - СписокЗначений[е];
КонецЕсли;
КонецЦикла;

+(96) короче лень спорить, хошь проверяй, хошь нет.

(97) А как оператор Если ускорит эту конструкцию?

(101) Он не ускорит. Он защитит от нулевого индекса

(100) Работать не будет.
"короче лень спорить, хошь проверяй, хошь нет" (с)

(99) Да. Такой, по идее, рабочий. Но тут уже есть арифметические операции :) Плюс алгоритм не универсальный. Короче, нечто среднее по производительности и универсальности получается.

(102) Дык, у массива индексация с 0

(105) в 1c - с нуля? Не знал... ЖКК глянуть надо... Но ленб

(77) А причем здесь "Юмор"? ) Тема то серьезная

(106) Массив (Array) Возможно обращение к значению элемента посредством оператора [...]. В качестве аргумента передается индекс значения (нумерация с 0).

В одном байте восемь бит.

(109) Спасибо за информацию! ))

(109) А восемь ваххабитов - это один ваххабайт...
1 терапевт - 1024 гигапевта...

Мне, я уже говорил, больше всего алгоритм из (32) импонирует. Простой, работает для любого числа, время выполнения пропорционально величине числа. Время выполнения практически не медленнее остальных вариантов (у 1С разницы по времени между элементарными операциями почти нет - её съедают накладные расходы интерпретации). Если время критично - тогда уже табличка. Компромиссы бессмысленны.

В общем, даже такой высокоуровневый язык как 1С не помеха для работы с чем угодно и к тому же с приемлемой производительностью. Все дело в голове )

(113) ASM по-любэ быстрее будет. Хотя бы потому что компилятор

А извращятся конечно по-разному можно

+(114) ну и естественней делать по циклу, правый или левый сдвиг через флаг переноса, или через массив, но сказать что будет быстрее сможет только замер, причем на разных процессорах будет по разному

(116) Ты что? Через массив без вариантов быстрее. На каких процессорах не сравнивай.

(117) спекулятивное выполнение может проканать и будет быстрее, а с доступом в массив возникнут сложности: будет ли он в кеше ну и т. д.

(113) Никто и не спорит. Но за глаза хватит и реализации на 1С

Ужас

(118) Ну такие функции используются обычно в циклах да еще к тому же в совокупности с другими вычислениями. Так что кеш будет валиден после первой итерации и эффект от спекуляции доступа к памяти с остальными операциями в совокупности выше чем сдвиг по циклу, даже развернутый.

(121) Сложно скзать нужно мерить. Наверное тут все таки может быть пороговое значение от количества вызовов подсчета битов, когда будет быстрее тот или другой вариант. Но без замеров сказать сложно.

СтрЧислоВхождений(Строка(Число), "1") не?

(123) Не! :)

(124) а в чем сакральность сделать это именно с числом? )

Сколько установленных битов в числе "112"? 2? На самом деле 3.

(126) не факт =)

(17) Мда ... а в школе на информатике теперь ворд изучают ...

(128) Мне нужен очень быстрый алгоритм. В школе такому не учат )

(103) Как же меня задолбали такие умники:
Процедура КнопкаВыполнитьНажатие(Кнопка)
   Перем Временно, Результат, Бит;
   Бит = 128;
   Результат = "";
   
   Временно = Десятичное;
   Пока Бит >= 1 Цикл
       Если Временно >= Бит Тогда
           Результат = Результат + "1";
           Временно = Временно - Бит;
       Иначе
           Результат = Результат + "0";
       КонецЕсли;
       Бит = Бит / 2;
   КонецЦикла;
   Сообщить(Результат);
КонецПроцедуры

Ну где этот умник фишер?

(0)
учат в школе так

Ч%2+
Цел(Ч/2)%2+
Цел(Ч/4)%2+
Цел(Ч/8)%2+
Цел(Ч/16)%2+
Цел(Ч/32)%2+
Цел(Ч/64)%2+
Цел(Ч/128)

+(132)
но (130) красивше.

Что бы быстро считало нужно все циклы развернуть и сделать кейс из 256 случаев

(134)
ну уж лучше без кейса.
в массив или лучше в соответствие засунуть.

(135) Хм, лучше в соответствие чем в массив? Поиск O(log N) лучше чем O(1)?

(136)
наверное, да, для фиксированного массива O(1) (что-забыл про него).
для обычного - сильно сомневаюсь, скорее всего O(N).

(137) С чего это вдруг для обычного O(n), если доступ по индексу?

(131) Виноват. Невнимательно читал. Решил, что твоё предложение идентично (91), а там вычитания не было.

(132) Вариант в (32) отработает быстрее для небольших чисел плюс он более универсален.

(132)
К сожалению, в 1С нет оператора целочисленного деления, поэтому, если мы выполняем деление - то переходим в дробные числа, которые нужно округлять.
Понятно, что в Visual Basic мы радостно пишем Число\2 и не имеем проблем с потерей производительности.
(137) Поиск по массиву из 256 элементов, это одна индексная операция сложения адреса поэтому О(1).

Однако, если число больше одного байта, то уже начинаются сложности, так как для двух байтов массив уже съест достаточно памяти (65536*4+21).

Исправил чуток:

Процедура КнопкаВыполнитьНажатие(Кнопка)
   Перем Временно, Результат, Бит;
   
   Временно = Десятичное;
   Результат = "";
   
   Бит = 1;
   Пока Бит * 2 <= Временно Цикл
       Бит = Бит * 2;
   КонецЦикла;
   
   Пока Бит >= 1 Цикл
       Если Временно >= Бит Тогда
           Результат = Результат + "1";
           Временно = Временно - Бит;
       Иначе
           Результат = Результат + "0";
       КонецЕсли;
       Бит = Бит / 2;
   КонецЦикла;
   
   Пока СтрДлина(Результат) / 8 <> Цел(СтрДлина(Результат) / 8) Цикл
       результат = "0" + Результат;
   КонецЦикла;
   
   Сообщить(Результат);
КонецПроцедуры

(141) или две индексные операции плюс одна сложения :) (для двух байт)

(0) и давно ты программист?

вернее так:

и давно ты "программист"?

(138) (141)
потому что физически массив в 1С - это, скорее всего, список. т.к.
трудно представить метод Добавить() у классического массива.

(144) 20 лет где-то

(146) Фи, практически любая реализация классического массива в любом языке имеет метод Добавить. Например STL vectort

насчет массива

Массив256 = Новый Массив;
Массив256.Добавить(0);

Пока Массив256.Количество() < 256 Цикл
   Для к = 0 по Массив256.Вграница() Цикл
            Массив256.Добавить(1 + Массив256[к]);  
   КонецЦикла;
КонецЦикла;

(148)
да.
но это уже не O(1).

(148) Так речь не про сложность Добавить, а про сложность []

(148)
насчет любого языка - неправда.

(152) В тех, которые я знаю, правда )

(151)
когда  объявляется массив - выделяется память размером N*L, где
N - колво элементов, L - размер элемента.
при обращении по индексу - да O(1).
но как в этот массив можно Добавить()?
так что в 1С это список, может и индексирован(что сомнительно)
.
про фиксированный массив не знаю.

(153)
понятно.
ассемблеров, алголов, фортранов, паскалей, С не признаешь.

(154)
- В любом объектно (ориентированном) языке есть классы, которые реализуют понятие массива, а в структурных соответвующее API, с методом Добавить. От фиксированого массива толку мало в общеприкладной разработке
- В 1С это элементарно проверить, достаточно сравнить скорость [] массива и структуры, например )

(156) Бедняга...

(155) Нет, просто в этих языках пользуют библиотеки функций для работы с контейнерами. В принципе это ничем не отличается от объектов, кроме как видом.

(157) А кому сейчас легко )

(156)
на ТЗ, проверял на 77.  O(N).

(160) ТЗ это вещь достаточно сложная. Как минимум это двумерный массив. Но с учетом поддержки индексов, столбцов и прочего, внутренняя структура скорее всего достаточно сложна.

(161)
да.
но классический двумерный массив = O(1).

(162) Но ТЗ это не классический двумерный массив )

(163)
да.
как и массив.

(164) Массив простой как дырка от бублика. А ТЗ более продвинутая вещь. Да и опыты   показывают, что у массива операция [] имеет сложность О(1).