Как подсчитать ведущие нули в Int32? Так что я хочу сделать, это написать функцию, которая возвращает 30, если мой вход Int32 равен 2, потому что в двоичном я имею 0000000000000010.
Считайте начальные нули в Int32
Ответ 1
Давайте возьмем число 20 в качестве примера. Это может быть указано в двоичном виде следующим образом:
00000000000000000000000000010100
Сначала мы "размазываем" самый значимый бит по младшим битовым позициям, сдвигая вправо и побитово-ИЛИ по себе.
00000000000000000000000000010100
or 00000000000000000000000000001010 (right-shifted by 1)
is 00000000000000000000000000011100
затем
00000000000000000000000000011100
or 00000000000000000000000000000111 (right-shifted by 2)
is 00000000000000000000000000011111
Здесь, поскольку это небольшое число, мы уже завершили работу, но, повторяя процесс вплоть до 16-битного сдвига вправо, мы можем гарантировать, что для любого 32-разрядного числа мы установили все биты от 0 до старшего разряда от исходного числа до 1.
Теперь, если мы посчитаем число 1 в нашем "размазанном" результате, мы можем просто вычесть его из 32, и у нас останется число ведущих нулей в исходном значении.
Как мы посчитаем количество установленных бит в целом числе? На этой странице есть волшебный алгоритм, который делает именно это ("алгоритм SWAR с переменной точностью для выполнения сокращения дерева"... если вы его получите, вы умнее меня!), что означает С# следующим образом:
int PopulationCount(int x)
{
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return (x & 0x0000003f);
}
Путем встраивания этого метода в наш метод "размазывания", описанный выше, мы можем создать очень быстрый, без циклов и без условных методов подсчет ведущих нулей целого числа.
int LeadingZeros(int x)
{
const int numIntBits = sizeof(int) * 8; //compile time constant
//do the smearing
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
//count the ones
x -= x >> 1 & 0x55555555;
x = (x >> 2 & 0x33333333) + (x & 0x33333333);
x = (x >> 4) + x & 0x0f0f0f0f;
x += x >> 8;
x += x >> 16;
return numIntBits - (x & 0x0000003f); //subtract # of 1s from 32
}
Ответ 2
Если вы хотите смешать код сборки для максимальной производительности. Вот как вы это делаете на С#.
Сначала поддерживающий код, чтобы сделать это возможным:
using System.Runtime.InteropServices;
using System.Runtime.CompilerServices;
using static System.Runtime.CompilerServices.MethodImplOptions;
/// <summary> Gets the position of the right most non-zero bit in a UInt32. </summary>
[MethodImpl(AggressiveInlining)] public static int BitScanForward(UInt32 mask) => _BitScanForward32(mask);
/// <summary> Gets the position of the left most non-zero bit in a UInt32. </summary>
[MethodImpl(AggressiveInlining)] public static int BitScanReverse(UInt32 mask) => _BitScanReverse32(mask);
[DllImport("kernel32.dll", SetLastError = true)]
private static extern IntPtr VirtualAlloc(IntPtr lpAddress, uint dwSize, uint flAllocationType, uint flProtect);
private static TDelegate GenerateX86Function<TDelegate>(byte[] x86AssemblyBytes) {
const uint PAGE_EXECUTE_READWRITE = 0x40;
const uint ALLOCATIONTYPE_MEM_COMMIT = 0x1000;
const uint ALLOCATIONTYPE_RESERVE = 0x2000;
const uint ALLOCATIONTYPE = ALLOCATIONTYPE_MEM_COMMIT | ALLOCATIONTYPE_RESERVE;
IntPtr buf = VirtualAlloc(IntPtr.Zero, (uint)x86AssemblyBytes.Length, ALLOCATIONTYPE, PAGE_EXECUTE_READWRITE);
Marshal.Copy(x86AssemblyBytes, 0, buf, x86AssemblyBytes.Length);
return (TDelegate)(object)Marshal.GetDelegateForFunctionPointer(buf, typeof(TDelegate));
}
Затем здесь сборка для генерации функций:
[UnmanagedFunctionPointer(CallingConvention.Cdecl)]
private delegate Int32 BitScan32Delegate(UInt32 inValue);
private static BitScan32Delegate _BitScanForward32 = (new Func<BitScan32Delegate>(() => { //IIFE
BitScan32Delegate del = null;
if(IntPtr.Size == 4){
del = GenerateX86Function<BitScan32Delegate>(
x86AssemblyBytes: new byte[20] {
//10: int32_t BitScanForward(uint32_t inValue) {
0x51, //51 push ecx
//11: unsigned long i;
//12: return _BitScanForward(&i, inValue) ? i : -1;
0x0F, 0xBC, 0x44, 0x24, 0x08, //0F BC 44 24 08 bsf eax,dword ptr [esp+8]
0x89, 0x04, 0x24, //89 04 24 mov dword ptr [esp],eax
0xB8, 0xFF, 0xFF, 0xFF, 0xFF, //B8 FF FF FF FF mov eax,-1
0x0F, 0x45, 0x04, 0x24, //0F 45 04 24 cmovne eax,dword ptr [esp]
0x59, //59 pop ecx
//13: }
0xC3, //C3 ret
});
} else if(IntPtr.Size == 8){
del = GenerateX86Function<BitScan32Delegate>(
//This code also will work for UInt64 bitscan.
// But I have it limited to UInt32 via the delegate because UInt64 bitscan would fail in a 32bit dotnet process.
x86AssemblyBytes: new byte[13] {
//15: unsigned long i;
//16: return _BitScanForward64(&i, inValue) ? i : -1;
0x48, 0x0F, 0xBC, 0xD1, //48 0F BC D1 bsf rdx,rcx
0xB8, 0xFF, 0xFF, 0xFF, 0xFF, //B8 FF FF FF FF mov eax,-1
0x0F, 0x45, 0xC2, //0F 45 C2 cmovne eax,edx
//17: }
0xC3 //C3 ret
});
}
return del;
}))();
private static BitScan32Delegate _BitScanReverse32 = (new Func<BitScan32Delegate>(() => { //IIFE
BitScan32Delegate del = null;
if(IntPtr.Size == 4){
del = GenerateX86Function<BitScan32Delegate>(
x86AssemblyBytes: new byte[20] {
//18: int BitScanReverse(unsigned int inValue) {
0x51, //51 push ecx
//19: unsigned long i;
//20: return _BitScanReverse(&i, inValue) ? i : -1;
0x0F, 0xBD, 0x44, 0x24, 0x08, //0F BD 44 24 08 bsr eax,dword ptr [esp+8]
0x89, 0x04, 0x24, //89 04 24 mov dword ptr [esp],eax
0xB8, 0xFF, 0xFF, 0xFF, 0xFF, //B8 FF FF FF FF mov eax,-1
0x0F, 0x45, 0x04, 0x24, //0F 45 04 24 cmovne eax,dword ptr [esp]
0x59, //59 pop ecx
//21: }
0xC3, //C3 ret
});
} else if(IntPtr.Size == 8){
del = GenerateX86Function<BitScan32Delegate>(
//This code also will work for UInt64 bitscan.
// But I have it limited to UInt32 via the delegate because UInt64 bitscan would fail in a 32bit dotnet process.
x86AssemblyBytes: new byte[13] {
//23: unsigned long i;
//24: return _BitScanReverse64(&i, inValue) ? i : -1;
0x48, 0x0F, 0xBD, 0xD1, //48 0F BD D1 bsr rdx,rcx
0xB8, 0xFF, 0xFF, 0xFF, 0xFF, //B8 FF FF FF FF mov eax,-1
0x0F, 0x45, 0xC2, //0F 45 C2 cmovne eax,edx
//25: }
0xC3 //C3 ret
});
}
return del;
}))();
Чтобы сгенерировать сборку, я запустил новый проект VС++, создал нужные мне функции, затем перешел в Debug → Windows → Disassembly. Для параметров компилятора я отключил inlining, включил intrinsics, предпочитал быстрый код, пропущенные указатели на фреймы, отключил проверки безопасности и проверки SDL. Код для этого:
#include "stdafx.h"
#include <intrin.h>
#pragma intrinsic(_BitScanForward)
#pragma intrinsic(_BitScanReverse)
#pragma intrinsic(_BitScanForward64)
#pragma intrinsic(_BitScanReverse64)
__declspec(noinline) int _cdecl BitScanForward(unsigned int inValue) {
unsigned long i;
return _BitScanForward(&i, inValue) ? i : -1;
}
__declspec(noinline) int _cdecl BitScanForward64(unsigned long long inValue) {
unsigned long i;
return _BitScanForward64(&i, inValue) ? i : -1;
}
__declspec(noinline) int _cdecl BitScanReverse(unsigned int inValue) {
unsigned long i;
return _BitScanReverse(&i, inValue) ? i : -1;
}
__declspec(noinline) int _cdecl BitScanReverse64(unsigned long long inValue) {
unsigned long i;
return _BitScanReverse64(&i, inValue) ? i : -1;
}
Ответ 3
Попробуйте следующее:
static int LeadingZeros(int value)
{
// Shift right unsigned to work with both positive and negative values
var uValue = (uint) value;
int leadingZeros = 0;
while(uValue != 0)
{
uValue = uValue >> 1;
leadingZeros++;
}
return (32 - leadingZeros);
}
Ответ 4
Ниже приведены некоторые сложные ответы. Как насчет этого?
private int LeadingZeroes(int value)
{
return (32 - (Convert.ToString(value, 2).Length));
}
Хотя теперь я предполагаю, что могут быть некоторые проблемы с отрицательными числами и еще что-то с этим типом решения.
Ответ 5
Посмотрите https://chessprogramming.wikispaces.com/BitScan для хорошей информации о битскандинге.
Если вы можете смешивать код сборки, используйте современные команды процессора LZCNT, TZCNT и POPCNT.
Кроме этого, посмотрите на реализацию Java для Integer.
/**
* Returns the number of zero bits preceding the highest-order
* ("leftmost") one-bit in the two complement binary representation
* of the specified {@code int} value. Returns 32 if the
* specified value has no one-bits in its two complement representation,
* in other words if it is equal to zero.
*
* <p>Note that this method is closely related to the logarithm base 2.
* For all positive {@code int} values x:
* <ul>
* <li>floor(log<sub>2</sub>(x)) = {@code 31 - numberOfLeadingZeros(x)}
* <li>ceil(log<sub>2</sub>(x)) = {@code 32 - numberOfLeadingZeros(x - 1)}
* </ul>
*
* @param i the value whose number of leading zeros is to be computed
* @return the number of zero bits preceding the highest-order
* ("leftmost") one-bit in the two complement binary representation
* of the specified {@code int} value, or 32 if the value
* is equal to zero.
* @since 1.5
*/
public static int numberOfLeadingZeros(int i) {
// HD, Figure 5-6
if (i == 0)
return 32;
int n = 1;
if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n += 8; i <<= 8; }
if (i >>> 28 == 0) { n += 4; i <<= 4; }
if (i >>> 30 == 0) { n += 2; i <<= 2; }
n -= i >>> 31;
return n;
}
Ответ 6
Давай, ребята, перестань спрашивать: "Почему ты хочешь делать то или это". Ответьте, если вы можете или просто продолжать. Подсчет главных нулей является общей задачей во многих проблемах (например, алгоритмы сжатия). Для этого есть даже аппаратные инструкции x86 (clz, bsr). К сожалению, вы не можете использовать эти аппаратные инструкции на С#, потому что встроенные функции не поддерживаются (пока). Я полагаю, преобразование в строку было шуткой.
Двоичное представление int имеет очень четко определенные границы. На самом деле, в С# int есть просто псевдоним для Int32. Как указывает его namge, "Int32" всегда имеет 32-битное целое число со знаком, даже если вы скомпилируете свой проект для x64.
И вам не нужна специальная магия вуду для вычисления начальных нулей: Вот просто математическое решение, которое работает:
Здесь "x" - ваш int (Int32):
int LeadingZeros = (int)(32 - Math.Log((double)x + 1, 2d));
LeadingZeros += (int)((x - (0x80000000u >> LeadingZeros)) >> 31);
Изменить: Извините, я пересмотрел и исправил свою формулу. Из-за ошибок точности двойной арифметики результат может быть неверным для нескольких граничных случаев. Так что ему по-прежнему нужна "магия вуду". Вторая строка обрабатывает эти случаи и дает правильный результат.
Ответ 7
private int GetIntegerOffsetLength(int value)
{
return (32 - (Convert.ToString(value, 2).Length);
}
Ответ 8
В C:
unsigned int
lzc(register unsigned int x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return(WORDBITS - ones(x));
}
(from http://aggregate.org/MAGIC/#Leading Zero Count)
Перевод на С# оставлен как тривиальное упражнение для читателя.
ИЗМЕНИТЬ
Причина, по которой я дал ссылку, заключалась в том, что мне не нужно копировать следующее (снова в C):
#define WORDBITS 32
unsigned int
ones(unsigned int x)
{
/* 32-bit recursive reduction using SWAR...
but first step is mapping 2-bit values
into sum of 2 1-bit values in sneaky way
*/
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003f);
}
Ответ 9
32 - Convert.ToString(2,2).Count()
Ответ 10
подсчитать ведущие нули/найти первый набор/бит сканирования назад - такая общая вещь, которую нужно хотеть в ОС и других низкоуровневых программах, большинство аппаратных поддерживает clz в форме одной инструкции цикла. И большинство компиляторов c/С++ имеют встроенный компилятор.
http://en.wikipedia.org/wiki/Find_first_set
Кроме того, большинство аппаратных средств и компиляторов также имеют счетные нули, число совпадений/количество бит/счетчиков, четность, bswap/flip endien и несколько других квари, но очень полезных операций с битами.
Ответ 11
Если вы просто хотите смоделировать инструкцию Lzcnt, вы можете сделать это следующим образом (она дает 32 для нулевого значения):
int Lzcnt(uint value)
{
//Math.Log(0, 2) is -Infinity, cast to int is 0x80000000
int i=(int)Math.Log(value, 2);
return 31-(i&int.MaxValue)-(i>>31);
}
Если вам нужно знать, сколько бит необходимо для хранения определенного значения, лучше будет:
1+((int)Math.Log(value, 2)&int.MaxValue)
Выше даёт единицу для нулевого значения - так как вам нужен один бит для хранения нуля.
Но они будут работать только для uint, а не для ulong. Double (который является аргументом метода Log) не обладает достаточной точностью для хранения длинны до младшего бита, поэтому (double)0xFFFFFFFFFFFFFF неотличим от (double)0x100000000000000.
Но с .Net Core 3.0 мы наконец получили самую последнюю и лучшую доступную инструкцию Lzcnt. Так что если только System.Runtime.Intrinsics.X86.Lzcnt.IsSupported (System.Runtime.Intrinsics.X86.Lzcnt.X64.IsSupported для ulong), то вы можете использовать System.Runtime.Intrinsics.X86.Lzcnt.LeadingZeroCount(value) (System.Runtime.Intrinsics.X86.Lzcnt.X64.LeadingZeroCount(value) для ulong).
Ответ 12
Я думаю, что лучший выбор - спонсор пост выше. Однако, если кто-то ищет небольшое повышение производительности, можно использовать следующее.. (примечание: в тестах на моей машине это только на 2% быстрее)
Это работает путем преобразования числа с плавающей точкой в int и последующего захвата битов экспоненты.
[StructLayout(LayoutKind.Explicit)]
private struct ConverterStruct
{
[FieldOffset(0)] public int asInt;
[FieldOffset(0)] public float asFloat;
}
public static int LeadingZeroCount(uint val)
{
ConverterStruct a; a.asInt = 0; a.asFloat = val;
return 30-((a.asInt >> 23 )) & 0x1F;
}
Это также можно распространить на версию для Int64...
[StructLayout(LayoutKind.Explicit)]
private struct ConverterStruct2
{
[FieldOffset(0)] public ulong asLong;
[FieldOffset(0)] public double asDouble;
}
// Same as Log2_SunsetQuest3 except
public static int LeadingZeroCount(ulong val)
{
ConverterStruct2 a; a.asLong = 0; a.asDouble = val;
return 30-(int)((a.asLong >> 52)) & 0xFF;
}
Примечание: Идея использования показателя в выражении взята из SPWorley 22.03.2009. Используйте с осторожностью в производственном коде, так как это может не сработать на архитектурах, которые не имеют порядка байтов.
Вот некоторые тесты для Floor-Log2 - это почти то же самое: https://github.com/SunsetQuest/Fast-Integer-Log2)
Ответ 13
Вы можете получить лучшую производительность с использованием предварительно вычисленных счетчиков
public static class BitCounter
{
private static readonly int[] _precomputed = new[]
{
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
};
public static int CountOn(int value)
{
return _precomputed[value >> 24] +
_precomputed[(value << 8) >> 24] +
_precomputed[(value << 16) >> 24] +
_precomputed[value & 0xFF];
}
public static int CountOff(int value)
{
return 32 - CountOn(value);
}
}
Ответ 14
Целые числа не имеют ведущих нулей и не поддерживают 32 цифры. При этом вы должны иметь возможность создать функцию для этого, преобразовая целое число в строку и проверив длину:
private int GetIntegerOffsetLength(int value)
{
//change 32 to whatever your upper bound is
return (32 - (value.ToString().Length + 1));
}