Вирус переворота строки косит программистов - О работе

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

	От:	Vlad_SP
	Дата:	24.10.18 06:08
	Оценка:	+2 -1

Здравствуйте, Masterspline,

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

Чегоооо??? Тебе явно не приходилось сталкиваться с нестандартными архитектурами. А вот мне например приходилось сталкиваться с экзотической архитектурой, где в байте было 18 бит

Байт и октет — почувствуйте разницу!

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

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

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

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

	От:	CreatorCray
	Дата:	23.10.18 19:42
	Оценка:

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

Тё>Отличается тупизной: проверяет память кандидата. Ну по твоим ответам оно заметно.
Да, Артёмка, ignorance is bliss это про тебя.

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

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

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

	От:	CreatorCray
	Дата:	23.10.18 23:33
	Оценка:	+2

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

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

vsb>И это при том, что в процессоре есть специальная команда как раз для этой задачи: POPCNT.
Упоминание POPCNT будет плюсом, но будет предложено вернутся к обсуждению алгоритма.

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

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

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

	От:	pagid
	Дата:	25.10.18 16:06
	Оценка:	+2

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

V_S>Чегоооо??? Тебе явно не приходилось сталкиваться с нестандартными архитектурами. А вот мне например приходилось сталкиваться с экзотической архитектурой, где в байте было 18 бит

Байт и октет — почувствуйте разницу!

И называлось оно слово (word), но никак не байт

Телеграфный "байт" не равен октету. В архитектурах 70-х иногда обмен с переферией шел 7-разряными "байтами". Вот в подобных случаях очень умозритетельно можно считать, что байт был не 8 бит

... << RSDN@Home 1.3.110 alpha 5 rev. 62>>

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

	От:	AlexMld
	Дата:	28.10.18 08:00
	Оценка:	10 (1)

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

P>Написавший путает разрядность сишного char и размер байта. В архитектурах с адресаций к словам, а не к байтам в С/С++ char имеет размер слова, а не байта.

В C++17 std::byte определяется следующим образом:

enum class byte : unsigned char {};

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0298r3.pdf

The C++ memory model

The fundamental storage unit in the C++ memory model is the byte. A byte is at least large enough to contain any member of the basic execution character set and the eight-bit code units of the Unicode UTF-8 encoding form and is composed of a contiguous sequence of bits, the number of which is implementation-defined.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf

Т.е. по определению в C++ количество бит в байте >= 8.

Отредактировано 28.10.2018 8:05 AlexMld . Предыдущая версия .

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 шт). И так постоянно удваивая размер группы можно считать для чисел бОльшей разрядности.

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

Вирус переворота строки косит программистов

От:	Тёмчик	жж
Дата:	22.10.18 23:25
Оценка:	+1

Пока я отсутствовал по причине первого сервиса мота, ещё один бакалавр в Computer Science пал жертвой коварного вопроса.

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

От:	Тёмчик	жж
Дата:	23.10.18 00:34
Оценка:

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

CC>Ты полгода назад ещё сам считал что "книжная задачка", "уныло", и не верил опытным товарищам.

Подсчёт битов ничего не говорит о человеке в плане bigO. Поэтому я и сейчас могу повторить- задачка унылая. Можно ещё спросить ieee 754 или перечислить ключи запуска jvm.

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

	От:	CreatorCray
	Дата:	23.10.18 03:55
	Оценка:	+1

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

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

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

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

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

	От:	CreatorCray
	Дата:	23.10.18 16:57
	Оценка:	+1

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

AN>Но вполне возможно, что оба участника собеседования могут сделать разные реализации, но реализация сделанная на собеседовании может и совпасть и не совпасть с тем, что ожидают от кандидата.
От кандидата ожидают исключительно демонстрации процесса мышления. Сама задача — лишь повод поговорить. Потому она очень простая и может быть решена разными способами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	От:	mmu
	Дата:	25.10.18 21:52
	Оценка:	+1

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

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

CC>Ты полгода назад ещё сам считал что "книжная задачка", "уныло", и не верил опытным товарищам.

Скучная задача, кандидат решит, что скучное место работы и покинет собеседование

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

	От:	CreatorCray
	Дата:	25.10.18 22:12
	Оценка:	+1

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

mmu>Скучная задача, кандидат решит, что скучное место работы и покинет собеседование

Ветер в спину

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

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

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

	От:	aik
	Дата:	29.10.18 11:22
	Оценка:

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

AM>В C++17 std::byte определяется следующим образом:
AM>

AM>enum class byte : unsigned char {};
AM>

ух ты ж ёжик, а для чего тут enum?

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

	От:	CreatorCray
	Дата:	22.10.18 23:42
	Оценка:

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

Тё>Пока я отсутствовал по причине первого сервиса мота, ещё один бакалавр в Computer Science пал жертвой коварного вопроса.
Ты полгода назад ещё сам считал что "книжная задачка", "уныло", и не верил опытным товарищам.

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

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

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

	От:	AleksandrN
	Дата:	23.10.18 09:33
	Оценка:

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

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

    return BITS_IN_BYTE[ byte ];
}

Для чисел большей размерности табличка слишком большой получится. В этом случае можно сложить сумму бит в каждом байте или посчитать с помощью сдвигов и битовых масок. Реализовать подсчёт битов в числе произвольного размера можно тоже по разному. В С++ можно сделать шаблонную функцию, а можно, в стиле C — функцию, в которой передаётся адрес, преобразованный к указателю на uint8_t и размер, а для подсчёта использовать таблицу. В других языках могут быть свои особенности.

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

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

	От:	vsb
	Дата:	23.10.18 17:11
	Оценка:

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

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

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

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

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

От:	Тёмчик	жж
Дата:	23.10.18 19:11
Оценка:

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

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

Можно ещё спросить ieee 754 или перечислить ключи запуска jvm.

Отличается тупизной: проверяет память кандидата. Ну по твоим ответам оно заметно.

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

	От:	Sharowarsheg
	Дата:	23.10.18 21:23
	Оценка:

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

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

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

Зависит от процессора. В общем случае неизвестно даже, есть ли в процессоре кэш, не говоря уж об SSE и прочем SIMD.

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

От:	Тёмчик	жж
Дата:	24.10.18 02:10
Оценка:

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

Тё>>Отличается тупизной: проверяет память кандидата. Ну по твоим ответам оно заметно.
CC>Да, Артёмка, ignorance is bliss это про тебя.

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

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

	От:	CreatorCray
	Дата:	24.10.18 02:47
	Оценка:

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

Тё>Ну считаешь, что трюки с битами отсекут любителей городить O(n*n) на ровном месте и парсить файл путём запихивания в память целиком- это твоё мнение.

Артёмка, ты так и не понял смысл подобных задач. Биты там не важны.

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

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

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

	От:	Masterspline
	Дата:	24.10.18 04:05
	Оценка:

AN> static const int BITS_IN_BYTE[] =

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

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

	От:	Masterspline
	Дата:	24.10.18 04:09
	Оценка:

S>Зависит от процессора. В общем случае неизвестно даже, есть ли в процессоре кэш, не говоря уж об SSE и прочем SIMD.

IMHO, это экзотика, когда ты не в курсе, пишешь ли ты программу под STM32f4 или i7, под винду или Мак. Используемые алгоритмы и архитектура софта также будет сильно зависеть от платформы (контроллер это или четырехсокетовый сервер). Так что обычно ты в курсе аппаратной архитектуры, оси и возможных версий сторонних библиотек, которые используются в проекте.

Отредактировано 24.10.2018 4:13 Ssd13 . Предыдущая версия .

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

От:	Тёмчик	жж
Дата:	24.10.18 04:37
Оценка:

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

CC>Артёмка, ты так и не понял смысл подобных задач. Биты там не важны.

Если чел не знает поведение битов- это не делает плохого программиста. А ты просто запомнил простейшую формулу n & (n-1)- совершенно тупой вопрос на память.

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

	От:	Sharowarsheg
	Дата:	24.10.18 04:51
	Оценка:

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

S>>Зависит от процессора. В общем случае неизвестно даже, есть ли в процессоре кэш, не говоря уж об SSE и прочем SIMD.

M>IMHO, это экзотика, когда ты не в курсе, пишешь ли ты программу под STM32f4 или i7, под винду или Мак. Используемые алгоритмы и архитектура софта также будет сильно зависеть от платформы (контроллер это или четырехсокетовый сервер). Так что обычно ты в курсе аппаратной архитектуры, оси и возможных версий сторонних библиотек, которые используются в проекте.

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

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

	От:	0xCAFEDEAD
	Дата:	24.10.18 04:59
	Оценка:

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

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

S>>>Зависит от процессора. В общем случае неизвестно даже, есть ли в процессоре кэш, не говоря уж об SSE и прочем SIMD.

M>>IMHO, это экзотика, когда ты не в курсе, пишешь ли ты программу под STM32f4 или i7, под винду или Мак. Используемые алгоритмы и архитектура софта также будет сильно зависеть от платформы (контроллер это или четырехсокетовый сервер). Так что обычно ты в курсе аппаратной архитектуры, оси и возможных версий сторонних библиотек, которые используются в проекте.

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

А есть ли там процессор вообще?

Про это может ничего и не сказано, а семантика языка и без процессора существует.

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

	От:	Sharowarsheg
	Дата:	24.10.18 05:10
	Оценка:

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

CAF>А есть ли там процессор вообще?

CAF>Про это может ничего и не сказано, а семантика языка и без процессора существует.

Тоже хороший вопрос.

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[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]: Вирус переворота строки косит программистов

	От:	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[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[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[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[13]: Вирус переворота строки косит программистов

	От:	Muxa
	Дата:	25.10.18 12:32
	Оценка:

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

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

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

	От:	Egorio
	Дата:	25.10.18 18:16
	Оценка:

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

Тё>Пока я отсутствовал по причине первого сервиса мота, ещё один бакалавр в Computer Science пал жертвой коварного вопроса.

Косит не программистов, а "программистов" которые по факту ими не являются

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

	От:	AlexMld
	Дата:	27.10.18 09:35
	Оценка:

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

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

V_S>>Чегоооо??? Тебе явно не приходилось сталкиваться с нестандартными архитектурами. А вот мне например приходилось сталкиваться с экзотической архитектурой, где в байте было 18 бит

Байт и октет — почувствуйте разницу!

P>И называлось оно слово (word), но никак не байт

P>Телеграфный "байт" не равен октету. В архитектурах 70-х иногда обмен с переферией шел 7-разряными "байтами". Вот в подобных случаях очень умозритетельно можно считать, что байт был не 8 бит

The size of the byte has historically been hardware dependent and no definitive standards existed that mandated the size – byte-sizes from 1 to 48 bits are known to have been used in the past.

https://en.wikipedia.org/wiki/Byte

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

	От:	pagid
	Дата:	27.10.18 10:13
	Оценка:

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

AM>

AM>The size of the byte has historically been hardware dependent and no definitive standards existed that mandated the size – byte-sizes from 1 to 48 bits are known to have been used in the past.

AM>https://en.wikipedia.org/wiki/Byte
А с забора определение не принесёте?

Возьмите любое описание архитектуры с адресацией к 16-18-32-48 разрядным словам, официальное, а не пересказ хабро-хипстерами, хоть современной, хоть исторической, и "байта" по отношению к минимально адресуемой ячейке памяти там не найдете, всегда "слово"

... << RSDN@Home 1.3.110 alpha 5 rev. 62>>

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

	От:	AlexMld
	Дата:	27.10.18 10:43
	Оценка:

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

AM>>https://en.wikipedia.org/wiki/Byte
P>А с забора определение не принесёте?

Ну, конечно, все дураки, один умный.

P>Возьмите любое описание архитектуры с адресацией к 16-18-32-48 разрядным словам, официальное, а не пересказ хабро-хипстерами, хоть современной, хоть исторической, и "байта" по отношению к минимально адресуемой ячейке памяти там не найдете, всегда "слово"

Не поверишь, существуют и 64-битные байты:
https://isocpp.org/wiki/faq/intrinsic-types#very-large-bytes

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

	От:	pagid
	Дата:	27.10.18 11:25
	Оценка:

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

AM>Ну, конечно, все дураки, один умный.
Почему один? Людей не путающихся в IT-терминах немало.

AM>Не поверишь, существуют и 64-битные байты:
AM>https://isocpp.org/wiki/faq/intrinsic-types#very-large-bytes

"I have heard..." это просто замечательно.
Написавший путает разрядность сишного char и размер байта. В архитектурах с адресаций к словам, а не к байтам в С/С++ char имеет размер слова, а не байта.

... << RSDN@Home 1.3.110 alpha 5 rev. 62>>

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

	От:	AlexMld
	Дата:	27.10.18 12:55
	Оценка:

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

P>"I have heard..." это просто замечательно.
P>Написавший путает разрядность сишного char и размер байта. В архитектурах с адресаций к словам, а не к байтам в С/С++ char имеет размер слова, а не байта.

У тебя какое-то узкое трактование понятия "байт". Байт — вовсе необязательно октет. В некоторых архитектурах байты вообще могли быть разного размера:

Some aspects of the instruction set are unusual, most notably the "byte" instructions, which operated on bit fields of any size from 1 to 36 bits inclusive according to the general definition of a byte as a contiguous sequence of a fixed number of bits.

https://en.wikipedia.org/wiki/PDP-10
http://pdp10.nocrew.org/docs/instruction-set/Byte.html

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

	От:	pagid
	Дата:	28.10.18 07:21
	Оценка:

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

AM>У тебя какое-то узкое трактование понятия "байт". Байт — вовсе необязательно октет.
О чем выше и писал приводя примеры — телеграфный байт, 7-битный байт для обмена с переферией в исторические времена.

AM> В некоторых архитектурах байты вообще могли быть разного размера:
AM>https://en.wikipedia.org/wiki/PDP-10
AM>http://pdp10.nocrew.org/docs/instruction-set/Byte.html

В PDP-10 DECовцы назвали "байтами" битовые поля переменной длинны, используемые в командах для упаковки/распаковки в машинное слово символьной и подобной инфы, дело их

Но обрати внимание, PDP-10 это архитектура с 36-битным словом, а вовсе не с 36-битным байтом. Именно на это я и обращал внимание с начале разговора — байт не во всех архитектурах минимально адресуемая область памяти. В архитектурах, где адрсация идет к 16-18-24-32-36-48-64 битовым участкам памяти, они называются не байт, а слово. И в PDP-10 точно так же.

... << RSDN@Home 1.3.110 alpha 5 rev. 62>>

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

	От:	pagid
	Дата:	29.10.18 11:15
	Оценка:

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

AM>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0298r3.pdf
AM>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf

AM>Т.е. по определению в C++ количество бит в байте >= 8.

Вполне возможно. Не разумно стандартом на язык заставлять реализацию программно упаковывать/распаковывать байты в слова и обратно. Но просто повторение ситуации с char

... << RSDN@Home 1.3.110 alpha 5 rev. 62>>

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

	От:	AleksandrN
	Дата:	29.10.18 11:42
	Оценка:

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

aik>ух ты ж ёжик, а для чего тут enum?

Обсуждение std::byte.

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

От:	Тёмчик	жж
Дата:	31.10.18 01:21
Оценка:

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

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

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

Меня исходники драйверов повергают в ужас. Треш и угар

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

	От:	CreatorCray
	Дата:	31.10.18 02:00
	Оценка:

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

Тё>Меня исходники драйверов повергают в ужас. Треш и угар

И?

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

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

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

От:	Тёмчик	жж
Дата:	31.10.18 02:04
Оценка:

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

Тё>>Меня исходники драйверов повергают в ужас. Треш и угар

CC>И?

Просто наблюдение

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

	От:	0xCAFEDEAD
	Дата:	31.10.18 06:48
	Оценка:

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

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

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

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

Тё>Меня исходники драйверов повергают в ужас. Треш и угар

Смотри сразу в бинарники тогда. В чем проблема

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

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

Заголовок: