Re[8]: Вирус переворота строки косит программистов - О работе

Re[5]: Вирус переворота строки косит программистов

	От:	Hobbes
	Дата:	24.10.18 06:18
	Оценка:

Здравствуйте, AleksandrN, Вы писали:

AN>Зависит от размера числа. Для 8-битного можно сделать так:
AN>

AN>int bits_cnt( uint8_t byte )
AN>{
AN>    static const int BITS_IN_BYTE[] =
AN>    {
AN>        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
AN>        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
AN>        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
AN>        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
AN>        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
AN>        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
AN>        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
AN>        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
AN>        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
AN>        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
AN>        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
AN>        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
AN>        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
AN>        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
AN>        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
AN>        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
AN>    };

AN>    return BITS_IN_BYTE[ byte ];
AN>}
AN>

А можно так:

popcnt8_intrin:
    popcntl %edi,%eax
    ret

Re[4]: Вирус переворота строки косит программистов

	От:	0xCAFEDEAD
	Дата:	24.10.18 06:49
	Оценка:

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, Тёмчик, Вы писали:

Тё>>Подсчёт битов ничего не говорит о человеке в плане bigO.
CC>Ты правда думаешь что это как то сильно отличается от переворота строки?

Похоже ты ничего не смыслишь в собеседованиях. Само слово БИТ уже ввергает кучу народа в ужас.

Re[6]: Вирус переворота строки косит программистов

	От:	AleksandrN
	Дата:	24.10.18 07:21
	Оценка:

Здравствуйте, Masterspline, Вы писали:

AN>> static const int BITS_IN_BYTE[] =

M>Неудачное название переменной. В байте всегда 8 бит.

В байте не обязательно 8 бит, хотя архитектуры с другим размером байта — редкость. Но то, что название неудачное — согласен.

Re[6]: Вирус переворота строки косит программистов

	От:	AleksandrN
	Дата:	24.10.18 07:54
	Оценка:

Здравствуйте, vsb, Вы писали:

vsb>Плохое решение. Выкидывать из кеша процессора линию забивая её мусором (а если будет много таких операций — ещё и кучу линий). И это при том, что в процессоре есть специальная команда как раз для этой задачи: POPCNT.

Вопрос в том, что хочет проверить собеседующий — знание алгоритмов и способность самостоятельно их придумывать/знание тонкостей архитектуры и компилятора/понятность кода/знание побитовых операций/... . И в зависимости от того, какие задачи предстоит решать и какие инструменты использовать, правильный ответ может быть разным.

А какой компилятор и какой код оптимизирует до POPCNT? Сделал подсчёт с помощью сдвигов и битовой маски, но gcc с опциями -O3 -msse4 просто развернул цикл, но POPCNT не использовал.

Re[7]: Вирус переворота строки косит программистов

	От:	·
	Дата:	24.10.18 08:09
	Оценка:	10 (2)

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

Re[7]: Вирус переворота строки косит программистов

	От:	vsb
	Дата:	24.10.18 10:26
	Оценка:

Здравствуйте, AleksandrN, Вы писали:

AN>А какой компилятор и какой код оптимизирует до POPCNT? Сделал подсчёт с помощью сдвигов и битовой маски, но gcc с опциями -O3 -msse4 просто развернул цикл, но POPCNT не использовал.

Компиляторозависимые интринсики надо использовать. Что-то вроде int __builtin_popcount. Ну или иметь в стандартной библиотеке такие функции и их оптимизировать при компиляции, такое видел в Rust и в Java. Ну или просто на язык ассемблера написать этот кусочек.

Кстати утяну с JDK реализацию с помощью битовой арифметики:

    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;

Это для 32-битов. Фиг его знает, как оно работает, но, по идее, если не использовать отдельные инструкции процессора, то такой код будет крайне быстр, т.к. это просто последовательность быстрых операций без ветвлений, обращений к памяти и прочей гадости, вжух по регистрам и всё.

Отредактировано 24.10.2018 10:30 vsb . Предыдущая версия . Еще …

Отредактировано 24.10.2018 10:30 vsb . Предыдущая версия .

Re[8]: Вирус переворота строки косит программистов

	От:	·
	Дата:	24.10.18 11:06
	Оценка:	8 (1)

Здравствуйте, vsb, Вы писали:

vsb>Кстати утяну с JDK реализацию с помощью битовой арифметики:
vsb>

vsb>    i = i - ((i >>> 1) & 0x55555555);
vsb>    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
vsb>    i = (i + (i >>> 4)) & 0x0f0f0f0f;
vsb>    i = i + (i >>> 8);
vsb>    i = i + (i >>> 16);
vsb>    return i & 0x3f;
vsb>

vsb>Это для 32-битов. Фиг его знает, как оно работает, но, по идее, если не использовать отдельные инструкции процессора, то такой код будет крайне быстр, т.к. это просто последовательность быстрых операций без ветвлений, обращений к памяти и прочей гадости, вжух по регистрам и всё.
Как я понимаю, первая строчка — это немного магии чтобы работать int без поддержки unsigned.
А работает оно просто и красиво. Берём число, например для простоты рассмотрим четырёхразрядное 1110, посчитаем вначале кол-во битов в каждоый группе из двух бит (11)(10). Для этого берём у него нечётные биты и чётные (справа налево): _1_0 и 1_1_ (в коде это наложение битовой маски оператором &). Сдвигаем вторую часть (оператор >>>), получается пара _1_0 и _1_1. Их сумма (оператор +) даёт количество битов в каждой паре _1_0 + _1_1 = (10)(01) т.е. (2 шт)(1 шт). Теперь делаем то же но для групп из четырёх бит: __01 и 10__, сдвигаем получается __01 и __10, складываем: __01 + __10 = 11 т.е. (3 шт). И так постоянно удваивая размер группы можно считать для чисел бОльшей разрядности.

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

Re[5]: Вирус переворота строки косит программистов

	От:	CreatorCray
	Дата:	24.10.18 15:36
	Оценка:

Здравствуйте, 0xCAFEDEAD, Вы писали:

CAF>Похоже ты ничего не смыслишь в собеседованиях. Само слово БИТ уже ввергает кучу народа в ужас.

Мы системщики. Тех, кого слово бит повергает в ужас нам сразу не надо.

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

Забанили по IP, значит пора закрыть эту страницу.
Всем пока

Re[9]: Вирус переворота строки косит программистов

	От:	CreatorCray
	Дата:	24.10.18 15:36
	Оценка:

Здравствуйте, Тёмчик, Вы писали:

Тё>Если чел не знает поведение битов- это не делает плохого программиста.
Таки делает, такой программист для нас сразу не годится.

Тё> А ты просто запомнил простейшую формулу n & (n-1)- совершенно тупой вопрос на память.

Ух какая тупизна! Ты совсем читать не умеешь.

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

Забанили по IP, значит пора закрыть эту страницу.
Всем пока

Re[9]: Вирус переворота строки косит программистов

	От:	CreatorCray
	Дата:	24.10.18 18:34
	Оценка:

Здравствуйте, Sharowarsheg, Вы писали:

S>Довольно странно с таким заданием начинать говорить о каких-то линиях кэша и прочих тонкостях, не спросив, а какой процессор и есть ли вообще кэш.
В ответ на вопросы "какой проц, какой кэш" будет отвечено что это irrelevant.

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

Забанили по IP, значит пора закрыть эту страницу.
Всем пока

Re[7]: Вирус переворота строки косит программистов

	От:	CreatorCray
	Дата:	24.10.18 18:34
	Оценка:

Здравствуйте, AleksandrN, Вы писали:

AN>Вопрос в том, что хочет проверить собеседующий
Способность придумывать варианты решения проблемы.
Потому что если человек не способен это делать он годится только в кодеры.

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

Забанили по IP, значит пора закрыть эту страницу.
Всем пока

Re[6]: Вирус переворота строки косит программистов

	От:	0xCAFEDEAD
	Дата:	24.10.18 20:14
	Оценка:

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, 0xCAFEDEAD, Вы писали:

CAF>>Похоже ты ничего не смыслишь в собеседованиях. Само слово БИТ уже ввергает кучу народа в ужас.

CC>Мы системщики. Тех, кого слово бит повергает в ужас нам сразу не надо.

Да уж понятно, что таких к железу секретному подпускать нельзя. Сломают еще, а оно небось подотчетное

Re[9]: Вирус переворота строки косит программистов

	От:	Muxa
	Дата:	24.10.18 21:57
	Оценка:

CC>>Артёмка, ты так и не понял смысл подобных задач. Биты там не важны.
Тё> А ты просто запомнил простейшую формулу n & (n-1)- совершенно тупой вопрос на память.
Ты правда думаешь что мы запоминаем такие формулы, а не выводим по месту?
Чувак, у меня для тебя плохие новости.

Re[10]: Вирус переворота строки косит программистов

От:	Тёмчик	жж
Дата:	25.10.18 03:54
Оценка:	-1

Здравствуйте, Muxa, Вы писали:

M>Ты правда думаешь что мы запоминаем такие формулы, а не выводим по месту?
M>Чувак, у меня для тебя плохие новости.

Ну там возможен всего один (оптимальный) вариант решения. Если вы (кстати, кто? социальная группа?) выходите что-то отличное от этого- то это песец из той же оперы, что с переворотом строки.

Re[11]: Вирус переворота строки косит программистов

	От:	CreatorCray
	Дата:	25.10.18 05:15
	Оценка:

Здравствуйте, Тёмчик, Вы писали:

Тё>Ну там возможен всего один (оптимальный) вариант решения.
No hire, sorry.

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

Забанили по IP, значит пора закрыть эту страницу.
Всем пока

Re[12]: Вирус переворота строки косит программистов

	От:	0xCAFEDEAD
	Дата:	25.10.18 05:31
	Оценка:

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, Тёмчик, Вы писали:

Тё>>Ну там возможен всего один (оптимальный) вариант решения.
CC>No hire, sorry.

А шанс все-таки был. Ээх.

Re[7]: Вирус переворота строки косит программистов

От:	Тёмчик	жж
Дата:	25.10.18 05:57
Оценка:

Здравствуйте, 0xCAFEDEAD, Вы писали:

CAF>Да уж понятно, что таких к железу секретному подпускать нельзя. Сломают еще, а оно небось подотчетное

Все биты поломают

Re[8]: Вирус переворота строки косит программистов

	От:	CreatorCray
	Дата:	25.10.18 07:48
	Оценка:

Здравствуйте, Тёмчик, Вы писали:

Тё>Все биты поломают

А потом положат в строку и отреверсят!

Жесть страхи какие!

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

Забанили по IP, значит пора закрыть эту страницу.
Всем пока

Re[11]: Вирус переворота строки косит программистов

	От:	Muxa
	Дата:	25.10.18 10:21
	Оценка:

Тё>Ну там возможен всего один (оптимальный) вариант решения.
И? Вот этот вариант и выводим.

Разных формул в природе миллионы.
Зачем их все запоминать, если можно один раз раобраться как работают простейшие арифметические и битовые операции, коих всего десяток.

Re[12]: Вирус переворота строки косит программистов

От:	Тёмчик	жж
Дата:	25.10.18 11:55
Оценка:	-1

Здравствуйте, Muxa, Вы писали:

Тё>>Ну там возможен всего один (оптимальный) вариант решения.
M>И? Вот этот вариант и выводим.

M>Разных формул в природе миллионы.
M>Зачем их все запоминать, если можно один раз раобраться как работают простейшие арифметические и битовые операции, коих всего десяток.

Это не кореллирует с пониманием bigO. Поэтому вопрос негодный.

|< 1 2 3 >|

Переместить
Удалить
Выделить ветку

Пока на собственное сообщение не было ответов, его можно удалить.

Заголовок: