Вопрос по c# – Считайте ведущие нули в Int32

9

Как мне посчитать лидирующие нули в Int32? Итак, я хочу написать функцию, которая возвращает 30, если мой ввод Int32 равен 2, потому что в двоичном коде у меня есть 0000000000000010.

Это странно похоже наthis question. Dan J
Это домашнее задание? Tejs
Должен ли он возвращать 30, поскольку для представления 2 требуется 2 бита 32-разрядного целого числа? Dan J
Но ... это значение не имеет 30 ведущих нулей. Jonathan Wood
Не могли бы вы еще раз объяснить, чего вы пытаетесь достичь, пожалуйста?int Безразлично & APOS; тhave "начальные нули" и строка "0000000000000010" не содержит 30 ничего. Что ты на самом деле пытаешься сделать? & quot; Подсчет лидирующих нулей & quot; не похоже на настоящую проблему. Dan J

Ваш Ответ

12   ответов
0
32 - Convert.ToString(2,2).Count()
0

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));
}

(отhttp://aggregate.org/MAGIC/#Leading Zero Count)

Перевод на C # оставлен читателю в качестве тривиального упражнения.

EDIT

Причина, по которой я дал ссылку, заключалась в том, что мне не нужно копировать следующее (снова в 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);
}
что такое WORDBITS и чтоones(x)? - ответ очень неполный в настоящее время в лучшем случае
Я думаю, что это просто перемещает основную часть работы вones(x)
5

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);
}
Я модифицировал способ для использования смещения целых чисел без знака, иначе с отрицательными значениями он никогда не выйдет из цикла.
0

ние битов - это обычное дело в ОС, и в других низкоуровневых программах большинство аппаратных средств поддерживают clz в виде инструкции с одним циклом. И большинство компиляторов c / c ++ имеют встроенный компилятор.

http://en.wikipedia.org/wiki/Find_first_set

Кроме того, большинство аппаратных средств и компиляторов также имеют конечные нули счетчика, поп-счет / бит-счет / счетчик-счетчики, четность, bswap / flip endien и некоторые другие нестандартные, но очень полезные операции перестановки битов.

1

ребята, перестаньте спрашивать "почему вы хотите сделать то или иное". Ответьте, если можете или просто продолжайте. Подсчет лидирующих нулей является распространенной задачей во многих задачах (например, алгоритмы сжатия). Для этого есть даже инструкции по аппаратному обеспечению x86 (clz, bsr). К сожалению, вы не можете использовать эти аппаратные инструкции в C #, потому что встроенные функции не поддерживаются (пока). Полагаю, преобразование в строку было шуткой.

Двоичное представление int имеет очень четкие границы. На самом деле, в C # int это просто псевдоним для Int32. Как следует из его названия, «Int32» всегда является 32-битным целым числом со знаком, даже если вы компилируете свой проект для x64.

И вам не нужна особая магия вудо для вычисления ведущих нулей: Вот простое математическое решение, которое работает:

Здесь & quot; x & quot; Ваш int (Int32):

int LeadingZeros = (int)(32 - Math.Log((double)x + 1, 2d));
LeadingZeros += (int)((x - (0x80000000u >> LeadingZeros)) >> 31);

Изменить: Извините, я рассмотрел и исправил мою формулу. Из-за ошибок точности двойной арифметики результат может быть неправильным для нескольких граничных случаев. Поэтому ему все еще нужно «волшебство вудо». Вторая строка обрабатывает эти случаи и дает правильный результат.

-3

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

private int GetIntegerOffsetLength(int value)
{
    //change 32 to whatever your upper bound is
    return (32 - (value.ToString().Length + 1));
}
Я думаю, что он хочет, чтобы он был преобразован в двоичный файл
@BrokenGlass: я знаю, какова максимальная длина целого числа. ОП специально попросил разницу от 32. Мой комментарий о корректировке верхней границы ожидал этого.
неправильный ответ - максимальная длина 32-битного целого числа в базе 10 не 32
3

private int LeadingZeroes(int value)
{
    return (32 - (Convert.ToString(value, 2).Length));
}

Хотя теперь я предполагаю, что могут быть некоторые проблемы с отрицательными числами и тому подобное с этим типом решения.

Хороший трюк, но медленный.
16

двоичном виде следующим образом:

    00000000000000000000000000010100

Сначала мы "мажем" самый значимый бит над младшими битовыми позициями путем смещения вправо и побитового ИЛИ над самим собой.

    00000000000000000000000000010100
 or 00000000000000000000000000001010 (right-shifted by 1)
 is 00000000000000000000000000011100

затем

    00000000000000000000000000011100
 or 00000000000000000000000000000111 (right-shifted by 2)
 is 00000000000000000000000000011111

Здесь, поскольку это небольшое число, мы уже завершили работу, но, повторяя процесс вплоть до 16-битного сдвига вправо, мы можем гарантировать, что для любого 32-битного числа мы установили все биты от 0 до MSB оригинального номера до 1.

Теперь, если мы посчитаем число 1 в нашем «размазанном» виде В результате мы можем просто вычесть его из 32, и у нас останется число ведущих нулей в исходном значении.

Как мы посчитаем количество установленных бит в целом числе?Эта страница имеет магический алгоритм для этого (& quot;a variable-precision SWAR algorithm to perform a tree reduction& quot; ... если ты это понял, ты умнее меня!), что переводится в C # следующим образом:

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
}
Привет большое спасибо. Мне было интересно, есть ли что-нибудь встроенное в C # для этого, хотя. Я приму это как "нет", учитывая, что я тоже ничего не нашел. richardstartin
Функция Единицы вычисляет вес Хэмминга. На странице википедии с таким названием приведено описание алгоритма.
закладкаaggregate.org/MAGIC, Это похоже на поразительную библию.
Также хочу добавить, что я сравнил это с приведением к удвоению и последующим чтением показательных битов. Эта реализация все еще быстрее. вес Хэмминга: 1550887 тиков, фпу: 1861061 тиков. Thats DateTime тикает за 10000000 итераций, кстати.
Как это волшебствоOnes функция работы?
3

оизводительности. Вот как вы это делаете в C #.

Сначала поддерживающий код, чтобы сделать это возможным:

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;
}))();

Чтобы сгенерировать сборку, я запустил новый проект VC ++, создал нужные функции, а затем пошел в Debug -> Windows -> Disassembly. Для опций компилятора я отключил встраивание, включил встроенные функции, одобрил быстрый код, пропустил указатели фреймов, отключил проверки безопасности и проверки 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;
}
Обратите внимание, что когда я тестировал его, на самом деле он работал медленнее в dotnet 4.7.2 из-за накладных расходов ~ 50 при переходе от управляемого к неуправляемому коду. Сборочные функции должны быть намного толще, чтобы компенсировать эти накладные расходы.
Какой классный способ встроенной сборки в C #! Я искал способ использовать BSR для этого. Стоит отметить, что это "должно" быть самым быстрым способом сделать это, но это также зависит от архитектуры (не так, что многие из нас используют .NET на чем угодно, кроме x86). Это требует больше голосов.
Это действительно интересно. Интересно, это же ветвление к C ++ / CLI? Вот как я обычно доставляю сборку в управляемое пространство, главным образом потому, что я могу контролировать сортировку. К сожалению, Core не собирается поддерживать C ++ / CLI, так что, надеюсь, накладные расходы улучшились.
-1

используя предварительно вычисленные значения

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);
    }
}
@ Calmarius Это правда, мой код является лишь частью решения.
Как правило, таблицы поиска работают быстрее только в тестах. В реальной работе они могут быть медленнее, потому что они требуют, чтобы таблица поиска находилась в кэше. Если это не так, то это ошибка кэша, и вы теряете циклы. Самые быстрые (и самые надежные) алгоритмы - это, как правило, чисто математические операции без ветвей или справочных таблиц.
Ваш алгоритм не считает начальные нули, но все нули. Не то, о чем спрашивает ОП.
3

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's complement binary representation
 * of the specified {@code int} value.  Returns 32 if the
 * specified value has no one-bits in its two's 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's 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;
}
1
private int GetIntegerOffsetLength(int value)
{
    return (32 - (Convert.ToString(value, 2).Length);
}

Похожие вопросы