Ход конём по битам. Шахматный Bitboard

[Akon32]

Дано: knightNr — номер клетки доски, где стоит конь (от 0 до 63).
Надо: movesCount — количество полей, куда он может пойти (от 2 до 8).

Почему бы не завести массив из 64 элементов по ~3 бита, чтобы извлекать из него цифры непосредственно? Или даже из 16 элементов, если учитывать симметрии доски?
Более того, близость коня к краю доски отсекает некоторые из его 8ми ходов, и, наверно, можно написать несложную функцию из if-ов для решения этой задачи.

[FFormula]

В конце статьи я даю ответ на этот вопрос. По поводу 3 битов — спасибо, отличная мысль.
Ещё одна причина — на практике часто нужно знать не только количество, но и сами ходы.

[old_bear]

Самый быстрый способ

POPCNT?

[iShrimp]

Обстоятельно о подсчёте единичных битов. Добавляйте в закладки!

[FFormula]

Шикарная статья, большое спасибо за наводку.

[CryptoPirate]

POPCNT?

Такая штука не на всех процессорах есть :-)

[old_bear]

Процессор без SSE4.2 в 2019 году?
Можно при отсутствии этого флага выводить ругательное сообщение с предложением таки поагредить систему. Или перейти к варианту Б.

[fougasse]

ARM?

[old_bear]

В ARM есть CNT.
На самом деле, мой первоначальный комментарий был к двоякости фразы «самый быстрый способ».

[CryptoPirate]

Может быть мелкий микроконтроллер, там тоже подобных инструкций может не быть.

[WinPooh73]

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

int CountBits(U64 b)
{
	if (b == 0)
		return 0;

	static const U64 mask_1 = LL(0x5555555555555555);   // 0101 0101 0101 0101 ...
	static const U64 mask_2 = LL(0x3333333333333333);   // 0011 0011 0011 0011 ...
	static const U64 mask_4 = LL(0x0f0f0f0f0f0f0f0f);   // 0000 1111 0000 1111 ...
	static const U64 mask_8 = LL(0x00ff00ff00ff00ff);   // 0000 0000 1111 1111 ...

	U64 x = (b & mask_1) + ((b >> 1) & mask_1);
	x = (x & mask_2) + ((x >> 2) & mask_2);
	x = (x & mask_4) + ((x >> 4) & mask_4);
	x = (x & mask_8) + ((x >> 8) & mask_8);

	U32 y = U32(x) + U32(x >> 32);
	return (y + (y >> 16)) & 0x3f;
}

[FFormula]

Спасибо, очень красивое, элегантное решение!

[fougasse]

А есть какой-то резон кроме эстетического делать статические переменные в функции?
Вы на какой архитектуре профилировали своё решение?

[jaiprakash]

Это быстрее работает при многократных вызовах функции. Так заполнение переменных происходит один раз при старте.

[fougasse]

я в курсе, вопрос — зачем внутри это делать, а не вне функции.

[Sdima1357]

Чтобы не засорять глобальную область видимости.
А вообще всем современным компиляторам данный static по фигу, поскольку «переменная» mask — константа.

[fougasse]

есть анонимные namespaces, и ф-ия на 30% меньше строк станет

[grmood]

С чего вы решили, что это именно ++?

[Akon32]

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

Или даже метод из стандартной библиотеки. И в реализации этого метода на java 8 лишь 17 арифметических и битовых операций, а не 21, как у вас.

код java.lang.Long#bitCount(Long)

public static int bitCount(long i) {
        i = i - ((i >>> 1) & 0x5555555555555555L);
        i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
        i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        i = i + (i >>> 32);
        return (int)i & 0x7f;
     }