OriginalGriff Ответов: 10

Задача кодирования: подсчитайте один бит в числе.

Учитывая тридцатидвухразрядное целочисленное значение в качестве параметра, напишите функцию или метод, чтобы вернуть число битов "1" в этом числе.

Поэтому, если вы передадите 42, он должен вернуть 3-42 десятичных знака-это 2A шестнадцатеричных или 101010 двоичных-следовательно, 3 "1" бита.

Особое внимание следует уделить тому, чтобы сделать его как можно более эффективным: петли-плохая идея!

Что я уже пробовал:

Постановка задачи в первый раз в жизни!
гостиная[^]

Richard Deeming

СПОЙЛЕР! :)

Это будет тривиально в Ява[^] и С++[^]! :)

Я предполагаю, что какая-то вариация метод Стэндфорда[^] будет работать лучше всего для других языков.

OriginalGriff

Может быть, тривиально - это зависит от того, кто написал функции и какой метод они использовали. Посмотрите на решение номер один, которое* выглядит * эффективным, пока вы не подумаете о том, что происходит за кулисами.

Richard Deeming

Я считаю, что C++ просто называет popcnt инструкция по поддерживаемым процессорам, которая примерно так же эффективна, как вы можете получить. :)

Jochen Arndt

Я все еще тестировал свой код, пока вы это писали :)

А если POPCNT не поддерживается, то есть (вероятно) хорошо известная страница о битных твид-хаках

Richard Deeming

Я не могу ни подтвердить, ни опровергнуть, что известная страница существует, ни что есть ссылка на нее в тексте спойлера выше. :)

Jochen Arndt

Уупс.

Я не видел и не испортил этого (прокрутил только немного вверх после публикации моего решения и распиливания вашего последнего комментария).

Chris Maunder

Это заставляет меня хотеть добавить большие пальцы вверх к комментариям ;)

PIEBALDconsult

С какой целью?

Richard Deeming

Для секретный генеральный план[^]:

Фаза 1) Подсчитайте количество битов " on " в 32-битном целочисленном числе.
Фаза 2) ???
Фаза 3) Прибыль!

:)

OriginalGriff

Фаза 3) мировое господство.
FTFY!

OriginalGriff

Он используется для измерения расстояния Хэмминга и для криптоанализа.
Кроме того, решение" немного крутить " - это замечательный образ мышления!

10 Ответов

Рейтинг:
76

Patrice T

Очевидно, что будет трудно превзойти инструкцию процессора popcnt.
В языках высокого уровня есть в основном 2 варианта:
- Подсчет битов 1 на 1, если размер данных удваивается, то это занимает вдвое больше времени.

int BitsCnt(unsigned long int Bits) {
    int Cnt=0;
    do {
        Cnt += Bits && 1;
        Bits = Bits >> 1;
    }
    while (Bits != 0)
    return Cnt;
}

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

- Подсчет битов с помощью параллельного программирования бедных, если размер данных удваивается, то требуется всего 1 шаг больше.
int BitsCnt(unsigned long int Bits) {
    Bits= (Bits && 0x55555555) + ((Bits >> 1) && 0x55555555);
    Bits= (Bits && 0x33333333) + ((Bits >> 2) && 0x33333333);
    Bits= (Bits && 0x0f0f0f0f) + ((Bits >> 4) && 0x0f0f0f0f);
    Bits= (Bits && 0x00ff00ff) + ((Bits >> 8) && 0x00ff00ff);
    Bits= Bits + (Bits >>16);
    return Bits&& 0xff;
}

Graeme_Grant

Очень популярен метод на паутине ... поисковая таблица будет быстрее.

Patrice T

Мое решение - это 2 метода, которые мне нравятся.
Это не должно быть исчерпывающим.

Рейтинг:
2

Jochen Arndt

Быстрый и грязный для Visual C++ с процессорами x86 (Intel Nehalem и AMD Barcelona или более поздние версии):

#include <iostream>
#include <stdlib.h>
#include <intrin.h> 

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	if (2 != argc)
	{
		cout << "Usage: Bitcount <32-bit value>" << std::endl;
		return 1;
	}

	TCHAR *stop;
	unsigned long u = _tcstoul(argv[1], &stop, 0);
	if (0 != *stop || u > _UI32_MAX)
	{
		cout << "Usage: Bitcount <32-bit value>" << std::endl;
		return 1;
	}

	cout << "The value " << u << " has " << __popcnt(u) << " bits set" << endl;

	return 0;
}

То __popcnt() функция-это внутренняя функция, которая вызывает x86 POPCNT инструкция.

[РЕДАКТИРОВАТЬ]
С использованием GCC __builtin_popcount() вместо этого и компилируйте с помощью -mpopcnt.
[/РЕДАКТИРОВАТЬ]

Рейтинг:
2

Richard Deeming

С момента копирования магический-вудо-бит-вертлявый код было бы обманом, вот очевидное и немного более понятное решение C# :

public static int CountSetBits(int value)
{
    int result = 0;
    for (int i = 0; i < 8; i++)
    {
        byte nibble = (byte)(value & 0xF);
        value >>= 4;

        switch (nibble)
        {
            case 1:
            case 2:
            case 4:
            case 8:
            {
                result += 1;
                break;
            }
            case 3:
            case 5:
            case 6:
            case 9:
            case 10:
            case 12:
            {
                result += 2;
                break;
            }
            case 7:
            case 11:
            case 13:
            case 14:
            {
                result += 3;
                break;
            }
            case 15:
            {
                result += 4;
                break;
            }
        }
    }

    return result;
}

Бенчмаркинг через BenchmarkDotNet[^]:
public static int CountSetBitsSlow(int value)
{
    int result = 0;
    for (int i = 0, bit = 1; i < 32; i++, bit <<= 1)
    {
        if ((value & bit) != 0)
        {
            result++;
        }
    }

    return result;
}

...

public class CountBitsBenchmark
{
    private readonly int _value;

    public CountBitsBenchmark()
    {
        _value = new Random().Next();
    }

    [Benchmark]
    public int CountSetBits()
    {
        return Int32BitCounter.CountSetBits(_value);
    }

    [Benchmark]
    public int CountSetBitsSlow()
    {
        return Int32BitCounter.CountSetBitsSlow(_value);
    }
}

Результаты:
           Method |       Mean |    StdDev |
----------------- |----------- |---------- |
     CountSetBits | 11.2227 ns | 0.0482 ns |
 CountSetBitsSlow | 26.1762 ns | 0.2472 ns |


РЕДАКТИРОВАТЬ: Небольшое улучшение от разворачивания цикла, хотя оно и делает код значительно длиннее:
[StructLayout(LayoutKind.Explicit)]
private struct Int32Bytes
{
    [FieldOffset(0)]
    public int Int32;

    [FieldOffset(0)]
    public readonly byte Byte0;

    [FieldOffset(1)]
    public readonly byte Byte1;

    [FieldOffset(2)]
    public readonly byte Byte2;

    [FieldOffset(3)]
    public readonly byte Byte3;
}

public static int CountSetBits2(int value)
{
    int result = 0;
    var bytes = new Int32Bytes { Int32 = value };

    switch (bytes.Byte0 & 0xF)
    {
        case 1:
        case 2:
        case 4:
        case 8:
        {
            result += 1;
            break;
        }
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 12:
        {
            result += 2;
            break;
        }
        case 7:
        case 11:
        case 13:
        case 14:
        {
            result += 3;
            break;
        }
        case 15:
        {
            result += 4;
            break;
        }
    }

    switch (bytes.Byte0 >> 4)
    {
        case 1:
        case 2:
        case 4:
        case 8:
        {
            result += 1;
            break;
        }
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 12:
        {
            result += 2;
            break;
        }
        case 7:
        case 11:
        case 13:
        case 14:
        {
            result += 3;
            break;
        }
        case 15:
        {
            result += 4;
            break;
        }
    }

    switch (bytes.Byte1 & 0xF)
    {
        case 1:
        case 2:
        case 4:
        case 8:
        {
            result += 1;
            break;
        }
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 12:
        {
            result += 2;
            break;
        }
        case 7:
        case 11:
        case 13:
        case 14:
        {
            result += 3;
            break;
        }
        case 15:
        {
            result += 4;
            break;
        }
    }

    switch (bytes.Byte1 >> 4)
    {
        case 1:
        case 2:
        case 4:
        case 8:
        {
            result += 1;
            break;
        }
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 12:
        {
            result += 2;
            break;
        }
        case 7:
        case 11:
        case 13:
        case 14:
        {
            result += 3;
            break;
        }
        case 15:
        {
            result += 4;
            break;
        }
    }

    switch (bytes.Byte2 & 0xF)
    {
        case 1:
        case 2:
        case 4:
        case 8:
        {
            result += 1;
            break;
        }
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 12:
        {
            result += 2;
            break;
        }
        case 7:
        case 11:
        case 13:
        case 14:
        {
            result += 3;
            break;
        }
        case 15:
        {
            result += 4;
            break;
        }
    }

    switch (bytes.Byte2 >> 4)
    {
        case 1:
        case 2:
        case 4:
        case 8:
        {
            result += 1;
            break;
        }
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 12:
        {
            result += 2;
            break;
        }
        case 7:
        case 11:
        case 13:
        case 14:
        {
            result += 3;
            break;
        }
        case 15:
        {
            result += 4;
            break;
        }
    }

    switch (bytes.Byte3 & 0xF)
    {
        case 1:
        case 2:
        case 4:
        case 8:
        {
            result += 1;
            break;
        }
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 12:
        {
            result += 2;
            break;
        }
        case 7:
        case 11:
        case 13:
        case 14:
        {
            result += 3;
            break;
        }
        case 15:
        {
            result += 4;
            break;
        }
    }

    switch (bytes.Byte3 >> 4)
    {
        case 1:
        case 2:
        case 4:
        case 8:
        {
            result += 1;
            break;
        }
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 12:
        {
            result += 2;
            break;
        }
        case 7:
        case 11:
        case 13:
        case 14:
        {
            result += 3;
            break;
        }
        case 15:
        {
            result += 4;
            break;
        }
    }

    return result;
}

Результаты:
           Method |       Mean |    StdDev |
----------------- |----------- |---------- |
     CountSetBits | 11.1346 ns | 0.1539 ns |
    CountSetBits2 |  8.2397 ns | 0.1248 ns |
 CountSetBitsSlow | 19.5581 ns | 0.1278 ns |


Правка 2:
С собой switch оператор для каждого байта, а не для каждого кусочка, скорость снова увеличивается. Но то же самое относится и к длине кода.
public static int CountSetBits3(int value)
{
    int result = 0;
    var bytes = new Int32Bytes { Int32 = value };

    switch (bytes.Byte0)
    {
        case 1:
        case 2:
        case 4:
        case 8:
        case 16:
        case 32:
        case 64:
        case 128:
        {
            result += 1;
            break;
        }
        case 3:
        case 5:
        case 6:
        case 9:
        case 10:
        case 12:
        case 17:
        case 18:
        case 20:
        case 24:
        case 33:
        case 34:
        case 36:
        case 40:
        case 48:
        case 65:
        case 66:
        case 68:
        case 72:
        case 80:
        case 96:
        case 129:
        case 130:
        case 132:
        case 136:
        case 144:
        case 160:
        case 192:
        {
            result += 2;
            break;
        }
        case 7:
        case 11:
        case 13:
        case 14:
        case 19:
        case 21:
        case 22:
        case 25:
        case 26:
        case 28:
        case 35:
        case 37:
        case 38:
        case 41:
        case 42:
        case 44:
        case 49:
        case 50:
        case 52:
        case 56:
        case 67:
        case 69:
        case 70:
        case 73:
        case 74:
        case 76:
        case 81:
        case 82:
        case 84:
        case 88:
        case 97:
        case 98:
        case 100:
        case 104:
        case 112:
        case 131:
        case 133:
        case 134:
        case 137:
        case 138:
        case 140:
        case 145:
        case 146:
        case 148:
        case 152:
        case 161:
        case 162:
        case 164:
        case 168:
        case 176:
        case 193:
        case 194:
        case 196:
        case 200:
        case 208:
        case 224:
        {
            result += 3;
            break;
        }
        case 15:
        case 23:
        case 27:
        case 29:
        case 30:
        case 39:
        case 43:
        case 45:
        case 46:
        case 51:
        case 53:
        case 54:
        case 57:
        case 58:
        case 60:
        case 71:
        case 75:
        case 77:
        case 78:
        case 83:
        case 85:
        case 86:
        case 89:
        case 90:
        case 92:
        case 99:
        case 101:
        case 102:

Graeme_Grant

Как он сравнивается с версией таблицы поиска с помощью FastBitCount что я выложил?

Richard Deeming

Неудивительно, что как только он настроен, ваш работает намного быстрее:

           Method |       Mean |    StdDev |
----------------- |----------- |---------- |
     CountSetBits |  8.4809 ns | 0.0045 ns |
    CountSetBits2 |  8.1834 ns | 0.0290 ns |
 CountSetBitsSlow | 24.2760 ns | 0.1701 ns |
   CountSetBitsGG |  1.2261 ns | 0.0051 ns |


Однако настройка занимает больше времени и требует дополнительных 64 Кб памяти, поскольку вы предварительно вычисляете и кэшируете результат для каждого 16-битного числа. :)

Graeme_Grant

Спасибо за это. Да, есть таблица для настройки, я мог бы разместить таблицу в коде, а не вычислять ее. Но я думаю, что основная функция соответствует "максимально эффективно" критерий. :)

Graeme_Grant

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

Richard Deeming

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

(Вероятно, именно поэтому эта страница теперь так долго загружается!)

Это компромисс между потреблением памяти и скоростью. Ваш использует 256 раз больше памяти, чтобы примерно удвоить скорость. Это до клиента, чтобы решить, что является более важным.

Но, конечно, ни одна из версий не будет превзойти волшебный бит-вертлявый вариант, на который я ссылался в комментариях к этому вопросу, или низкоуровневый popcnt опция доступна в C++ и ассемблере. :)

Graeme_Grant

МММ ... кто предложил жестко закодированную таблицу? Я действительно сказал:"я мог бы разместить таблицу в коде, а не вычислять ее". После того, как я написал это, я сделал это. Просто ты был быстрее в отправке, чем я...

Richard Deeming

:Д

OriginalGriff

Это не магия! Это математика! :смеяться:

Graeme_Grant

Поисковый стол был самым очевидным решением для скорости. [редактировать:] Напоминает мне старые добрые времена, когда скорость передачи данных была 9600 или меньше, а вычисления CRC32 использовали поисковые таблицы... :)

Рейтинг:
1

Graeme_Grant

Повышение скорости для решения 1... Сначала требуется затравка таблицы поиска, а затем вызов метода FastBitCount.

using System;

namespace FastBitCount
{
    class Program
    {
        static void Main(string[] args)
        {
            InitLookup();

            Console.WriteLine($"42 = {FastBitCount(42)}");
            Console.ReadKey();
        }

        static int FastBitCount(int num)
            => FastBitCount((uint)num);

        static int FastBitCount(uint num)
            => lookup[num & 0xFFFF] + lookup[num >> 16];

        static byte[] lookup = new byte[65536];
        static void InitLookup()
        {
            for (int i = 0; i < lookup.Length; i++)
                lookup[i] = GetOneBits(i);
        }

        static byte GetOneBits(int num)
            => (byte)Convert.ToString(num, 2)
                            .Split(new[] { '0' }, 
                                StringSplitOptions.RemoveEmptyEntries)
                            .Length;
    }
}

ОБНОВЛЕНИЕ: Чтобы ускорить запуск, я удалил расчет таблицы поиска и жестко закодировал ее.
using System;

namespace FastBitCount
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine($"42 = {FastBitCount(42)}");
            Console.ReadKey();
        }

        static int FastBitCount(int num)
            => FastBitCount((uint)num);

        static int FastBitCount(uint num)
            => lookup[num & 0xFFFF] + lookup[num >> 16];

        static byte[] lookup = new byte[0x10000] {
    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,
    //trimmed
    11,12,12,13,12,13,13,14,12,13,13,14,13,14,14,15,12,13,13,14,13,14,14,15,13,14,14,15,14,15,15,16
            };
    }
}
Ты можешь скачать проект[^] чтобы попробовать.

OriginalGriff

Не могли бы вы сделать нам всем одолжение, переместить ваш стол в файл и разместить ссылку? Это чертовски медленная загрузка страницы, которую вы вызываете, и это несправедливо по отношению к тем, у кого медленные или per-meg платежные соединения.

Graeme_Grant

уже в процессе этого...

Patrice T

Если поиск-это то, что я думаю, я бы ожидал, что он начнется с 0, 1, 1, 2, 1, 2, 2, 3

Graeme_Grant

Да... должно быть, вы скопировали не ту таблицу при создании поста ... исправлено.

Patrice T

Действительно, так будет лучше.

Рейтинг:
1

Ramza360 

public int GetOneBits(int number) {
    string hexNum = Convert.ToString(number, 2);
    string[] ones = hexNum.Split('0');
    return ones.Length;
}

public void Test() {
    int ones = GetOneBits(423);
    Console.WriteLine("Number of one bits = " + ones.ToString());
    
    // answer = 4;
}

OriginalGriff

Это противно неэффективно и просто "скрывает" циклы: есть два цикла и до 34 выделений кучи в них .Чистые методы!

Ramza360

да конечно

Ramza360

о, лол, ты хотел, чтобы это было эффективно. Хаха

Dave Kreskowiak

Важной частью задачи является чтение и понимание всех требований.

Ramza360

Ну, это, по крайней мере, очень быстро, хотя и неэффективно.

OriginalGriff

Вы засекли время? Вы можете быть удивлены ...

Dave Kreskowiak

Уххх... нет, это не так. Даже близко. Это самое медленное подчинение до сих пор.

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

Graeme_Grant

Небольшое исправление для вас...

string[] ones = hexNum.Split(new[] { '0' }, StringSplitOptions.RemoveEmptyEntries);

Рейтинг:
0

CPallini

Один C один (я знаю, что он очень похож на CountSetBits4 Ричарда).

uint8_t bits(uint32_t w)
{
  const uint8_t m[] =
  {
    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,
  };
  
  uint8_t * p = (uint8_t *) & w;
  
  uint8_t b = m[*p++];
  b += m[*p++];
  b += m[*p++];
  b += m[*p++];
  b += m[*p++];
  return b;
}

Graeme_Grant

Вы понимаете, что Ричард использовал мою идею таблицы поиска?

CPallini

Нет, я не понял. Это важно?

Graeme_Grant

lmao... Мне это льстит...

CPallini

Ну, на самом деле, я заканчиваю независимо с таким кодом. Отправив его, я с первого взгляда распознала сходство с тем, что было у Ричарда. Я не стал выяснять дальше.

Рейтинг:
0

Jochen Arndt

Выполнение некоторых вычислений в пределах удар shell script мне приходит в голову, что эта задача также может быть реализована с помощью оболочек, поддерживающих числовые вычисления:

[РЕДАКТИРОВАТЬ]
Были жалобы на то, что я жульничал, используя хорошо известный код.
Поэтому я решил предложить свое собственное решение, которое не является лучшим. Он использует петлю с Максом. 8 итераций. Если циклы нежелательны, их можно развернуть с помощью 8 строк кода. Но при небольших значениях, таких как 42, цикл работает лучше.
[/РЕДАКТИРОВАТЬ]

#!/bin/bash

# There must be one command line argument
if [ $# -ne 1 ]; then
    echo "Usage: $0 <unsigned integer value>"
    exit 1
fi

# Digits only; optionally as hex
if [[ ! ($1 =~ ^[0-9]+$ || $1 =~ ^0[xX][0-9a-fA-F]) ]]; then
    echo "'$1' is not an unsigned integer"
    exit 1
fi

# Calculate number of bits set
# Algorithm from https://graphics.stanford.edu/~seander/bithacks.html
#let "c=$1 - (($1 >> 1) & 0x55555555)"
#let "c=($c & 0x33333333) + (($c >> 2) & 0x33333333)"
#let "c=(($c + ($c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24"

# A new version of my own.
# Calculates the bit count for each nibble (4-bits) until
#  no more bits are set.
c=0
let "v=$1"
while [ $v -ne 0 ]; do
    let "c=c + ((0xe994 >> (($v & 7) << 1)) & 3) + (($v >> 3) & 1)"
    let "v=v >> 4"
done

echo "Value $1 has $c bits set"

Richard Deeming

Ну, мы все могли бы скопировать магический-вудо-бит-вертлявый код из Стэнфорда, но я думал, что это будет обман! :)

OriginalGriff

Я наполовину ожидал, что "кто-то" скопирует этот код:
https://www.codeproject.com/Tips/365002/A-Csharp-implementation-of-AI-MEMO-Item-Co
:смеяться:

Jochen Arndt

Было бы наглостью использовать решение, написанное тем, кто поставил задачу :)

Это очень хорошая книга!
Я не знал этого раньше, потому что, зная сайт Стэнфорда, у меня не было причин искать другие реализации.

OriginalGriff

Мне нравится, как кто-то сел и подсчитал это, и над его головой зажглась маленькая лампочка! :смеяться:
Раньше я писал PDP-ассемблер, в другой жизни...

Jochen Arndt

Но это то, что делает разработчик:
Используйте существующие алгоритмы вместо того, чтобы изобретать велосипед.

И должен быть хотя бы один, который просто делает это :)

Graeme_Grant

да, мы все могли бы это сделать... эти проблемы связаны с оригинальностью, а не с копированием кого-то другого!

Jochen Arndt

Я бы не опубликовал его, если бы уже не опубликовал другой. Сделал это только для того, чтобы иметь решение, использующее его, и показать, что оно не требует общего языка программирования.

Graeme_Grant

По крайней мере, сохраняйте оригинальность...

Рейтинг:
0

Paul Churchfield 

u8_t NumSetBits(u32_t arg)
{
	u8_t num_set_bits = 0;
	u8_t count;
	for(count=0; count<32; count++)
	{
		if((1U << count) & arg)
			num_set_bits++;
	}
	return num_set_bits;
}

int main(void)
{
	u32_t arg = 0xffff;
	u8_t ones;

	ones = 	NumSetBits(arg);
	printf("arg(%x) has (%d) set ones\n", arg, ones);
	return 0;
}

Maciej Los

Кажется, вы не читали требований: "Особое внимание следует уделить тому, чтобы сделать его максимально эффективным: петли-плохая идея!"

Рейтинг:
0

Ralf Meier

Что вы об этом думаете :

Function BitSum(intVar As Integer) As Integer

    If intVar = 0 Then Return 0

    Dim count As Integer = 0
    If intVar < 0 Then
        intVar -= Integer.MinValue
        count += 1
    End If
    count += (intVar Mod 2) + BitSum(intVar \ 2)

    Return count

End Function

OriginalGriff

Рекурсия - это "скрытый цикл"...

Richard Deeming

И один из них со значительно более высокими накладными расходами, чем не скрытый цикл! :)

Ralf Meier

Конечно... если у вас есть цель, которая изначально требует цикла, и вы пытаетесь реализовать ее без цикла, вы всегда получите более высокие накладные расходы ... Извините...

Ralf Meier

Хорошо ... если Рекурсия - это тоже цикл, то я не знаю другого способа решить эту проблему ... :(

OriginalGriff

Вот в чем суть проблем кодирования-в поиске альтернатив и умных алгоритмов, а не в грубом принуждении к решению.

Рейтинг:
0

jaket-cp

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

	public int GetEnumCnt(int Number){
		Enum32 EnumNumber = (Enum32) Number;
		int EnumCnt = 0;
		
		foreach (Enum32 EnumItem in Enum.GetValues(typeof(Enum32))){
			if (EnumNumber.HasFlag(EnumItem)){
//			if ((EnumNumber & EnumItem) != 0){
				EnumCnt++;
			}
		}
		
		return EnumCnt;
	}

	public enum Enum32 {
		//_00 = 0,	//0
		_01 = 1 << 0,	//1
		_02 = 1 << 1,	//2
		_03 = 1 << 2,	//4
		_04 = 1 << 3,	//8
		_05 = 1 << 4,	//16
		_06 = 1 << 5,	//32
		_07 = 1 << 6,	//64
		_08 = 1 << 7,	//128
		_09 = 1 << 8,	//256
		_10 = 1 << 9,	//512
		_11 = 1 << 10,	
		_12 = 1 << 11,	
		_13 = 1 << 12,	
		_14 = 1 << 13,	
		_15 = 1 << 14,	
		_16 = 1 << 15,	
		_17 = 1 << 16,	
		_18 = 1 << 17,	
		_19 = 1 << 18,	
		_20 = 1 << 19,	
		_21 = 1 << 20,	
		_22 = 1 << 21,	
		_23 = 1 << 22,	
		_24 = 1 << 23,	
		_25 = 1 << 24,	
		_26 = 1 << 25,	
		_27 = 1 << 26,	
		_28 = 1 << 27,	
		_29 = 1 << 28,	
		_30 = 1 << 29,	
		_31 = 1 << 30,	
		_32 = 1 << 31	
	}

Richard Deeming

Это не только имеет петлю, которая была специально упомянута в вопросе; но Enum.GetValues гораздо менее эффективен, чем простой for петля! :)

jaket-cp

Да, немного озорно, но это было похоже на решение 10 от ppolymorphe, так что я подумал, что все будет в порядке :) - ну, я думаю, что это/было похоже в любом случае.
Я должен был упомянуть, что именно решение ppolymorphe заставило меня задуматься о перечислении.
Просто хотел вытащить его оттуда - посмотреть, есть ли жизнеспособный способ сделать это :)