Задачка::Проверка бита

← →
Dimka Maslov © (2014-10-14 11:07) [0]

Дано: имеется целое число (n). Известно, что в нём установлен только один бит, остальные нули.
Требуется установить номер этого бита (i).

Возможные решения:
1) for (i = 0; n && (n & 1) == 0; n>>=1, i++);
2) i = (int)log2((double)n);
3) тупо через switch

Какие ещё могут быть варианты?

← →
Romkin © (2014-10-14 11:11) [1]

Массив.
Вообще зависит от разрядности этого самого числа.

← →
manaka © (2014-10-14 11:16) [2]

> Известно, что в нём установлен только один бит, остальные
> нули

Значит число есть степень 2
Номер бита=степень+1

← →
Юрий Зотов © (2014-10-14 11:22) [3]

2^x = n

x = Log2(n)

← →
manaka © (2014-10-14 11:23) [4]

i:=1; while n<>1 do begin n=n/2; i=i+1; end;

))))))

← →
MBo © (2014-10-14 11:24) [5]

Ассемблер, BSR/BSF

Бинарный поиск
if (x and $FFFF0000)>0 then Index := Index+16; и т.п.

← →
oldman © (2014-10-14 11:24) [6]

> Юрий Зотов © (14.10.14 11:22) [3]
> x = Log2(n)

x=log2(n)+1

← →
Юрий Зотов © (2014-10-14 11:33) [7]

> oldman © (14.10.14 11:24) [6]

Это зависит от соглашения о нумерации. Если оно не оговорено, то в мире IT биты принято нумеровать, начиная с нуля.

← →
Юрий Зотов © (2014-10-14 11:35) [8]

Кто тег не закрыл?

Теперь закрыт.

← →
Dimka Maslov © (2014-10-14 11:35) [9]

> Romkin © (14.10.14 11:11) [1]

Для 64 бит массив будет ооооооооооочень большим

> Юрий Зотов © (14.10.14 11:22) [3]

Вариант 2 получается

> manaka © (14.10.14 11:23) [4]

Вариант 1 получается

> MBo © (14.10.14 11:24) [5]

чё-то не понял

> oldman © (14.10.14 11:24) [6]

log2(1) = 0, а биты нумеруются от 0 до 31. так что всё правильно

← →
MBo © (2014-10-14 11:35) [10]

незакрытый тег, видимо, я оставил.

Погуглил - без ветвлений есть метод:
var i, x: integer; table: array[0..31] of Integer; begin for i := 0 to 31 do //инициализация, метод de Brujin table[ ( $077CB531 * ( 1 shl i ) ) shr 27 ] := i; x := 1 shl 17; Caption := IntToStr(table[(x * $077CB531) shr 27]);

← →
MBo © (2014-10-14 11:37) [11]

>чё-то не понял
Не понял про ассемблерные команды, или про бинарный поиск?

← →
Dimka Maslov © (2014-10-14 11:39) [12]

Про бинарный поиск

← →
MBo © (2014-10-14 11:46) [13]

r:=0; //индекс единичного бита будет тут if (x and $FFFF0000)>0 then r:=r+16; // бит в старшем слове if (x and $FF00FF00)>0 then r:=r+8; // бит в старшем байте одного из слов if (x and $F0F0F0F0)>0 then r:=r+4; // бит в старшем ниббле одного из байтов if (x and $CCCCCCCC)>0 then r:=r+2; //бит в одно из старших битов ниббла if (x and $AAAAAAAA)>0 then r:=r+1; //бит на нечетном месте $AA = bin10101010

← →
Дмитрий С © (2014-10-14 12:42) [14]

Неужели банальную подсветку так сложно сделать с первого раза? :))

← →
Inovet © (2014-10-14 15:59) [15]

> [14] Дмитрий С © (14.10.14 12:42)

Сделай

← →
Inovet © (2014-10-14 15:59) [16]

> [9] Dimka Maslov © (14.10.14 11:35)
> Для 64 бит массив будет ооооооооооочень большим

64 элемента и будет по условию задачи.

← →
Rouse_ © (2014-10-14 18:05) [17]

Самое быстрое, конечно BSR, если задача на оптимизацию по скорости

← →
MBo © (2014-10-14 18:37) [18]

> Самое быстрое, конечно BSR, если задача на оптимизацию по
> скорости

Не факт. Оно, кажется, конвейеры с панталыку сбивает.
Я 4 метода испытал на старом Athlon - с магическим умножением, бинарный поиск, и BSR дают примерно одно и то же время, а сдвиг числа вправо, пока бит не найдется - втрое большее на таком тесте:
for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndex(i); end;

← →
Dimka Maslov © (2014-10-14 19:20) [19]

> Самое быстрое, конечно BSR, если задача на оптимизацию по
> скорости

Проблема в том, что на 64 битах злые вредоносные существа не дают прямого доступа к ассемблеру. Вот и приходится извращаться.

← →
Pavia © (2014-10-14 19:21) [20]

> Не факт. Оно, кажется, конвейеры с панталыку сбивает.

Только если на микрокоде сделана.

← →
Rouse_ © (2014-10-14 19:24) [21]

> MBo © (14.10.14 18:37) [18]
> Не факт. Оно, кажется, конвейеры с панталыку сбивает.

uses Windows; function GetIndexBsr(Value: DWORD): Byte; assembler; asm bsr eax, eax end; function GetIndexMBo(Value: DWORD): Byte; begin Result := 0; //индекс единичного бита будет тут if (Value and $FFFF0000) > 0 then Result := Result + 16; // бит в старшем слове if (Value and $FF00FF00) > 0 then Result := Result + 8; // бит в старшем байте одного из слов if (Value and $F0F0F0F0) > 0 then Result := Result + 4; // бит в старшем ниббле одного из байтов if (Value and $CCCCCCCC) > 0 then Result := Result + 2; //бит в одно из старших битов ниббла if (Value and $AAAAAAAA) > 0 then Result := Result + 1; //бит на нечетном месте $AA = bin10101010 end; var I: Integer; S: DWORD; begin Randomize; S := GetTickCount; for I := 0 to 100000000 do GetIndexBsr(I); Writeln(GetTickCount - S); S := GetTickCount; for I := 0 to 100000000 do GetIndexMBo(I); Writeln(GetTickCount - S); Readln; end.

265
1778

← →
Rouse_ © (2014-10-14 19:27) [22]

PS^ тем более что GetIndexMBo(6) = 3.
Или я не тот алгритм взял?

← →
Rouse_ © (2014-10-14 19:28) [23]

> Dimka Maslov © (14.10.14 19:20) [19]
> Проблема в том, что на 64 битах злые вредоносные существа
> не дают прямого доступа к ассемблеру. Вот и приходится извращаться.

Приведенный в [21] код достаточно успешно компилируется и работает в 64 битах :)

← →
Rouse_ © (2014-10-14 19:34) [24]

Может и не в тему, но тоже хочу задачку для разминки мозга подкинуть.
Дан ряд чисел от единицы до N (к примеру если N = 6, то ряд выглядит как 1,2,3,4,5,6).
Задача: написать функцию возвращающую сумму всех чисел ряда. (При N = 6, результат 21)
Ограничения - функция не должна использовать цикл или рекурсию.

← →
Dimka Maslov © (2014-10-14 19:35) [25]

> Приведенный в [21] код достаточно успешно компилируется
> и работает в 64 битах :)

Смотря каких. Маздайный С++ говорит, что
error C4235: nonstandard extension used : "__asm" keyword not supported on this architecture

И всё. Приплыли.

← →
Rouse_ © (2014-10-14 19:38) [26]

Под арму чтоль компилишь?

← →
Rouse_ © (2014-10-14 19:39) [27]

под 64 битами все пахет в MS VC++ 2010

← →
MBo © (2014-10-14 19:39) [28]

> Или я не тот алгритм взял?

Тот. Входные данные некорректные - один бит должен быть установлен, я выделение младшего бита убрал. Это может повлиять на ветвления, но не настолько радикально. Видимо, другая архитектура ядра процессора сказывается. Вот мой полный тест.

var i, k, l: Integer; table: array[0..31] of Integer; t: DWord; function BitIndexBSR(Value: Integer): Integer; asm BSR EAX,EAX end; function BitIndexDeBruijn(Value: Integer): Integer; begin Result := table[(Value * $077CB531) shr 27]; end; function BitIndexSHR(Value: Integer): Integer; begin Result :=0; while (Value and 1) = 0 do begin Inc(Result); Value := Value shr 1; end; end; function BitIndexBinS(Value: Integer): Integer; begin result:=0; //индекс единичного бита будет тут if (Value and $FFFF0000)<>0 then result:=result+16; // бит в старшем слове if (Value and $FF00FF00)<>0 then result:=result+8; // бит в старшем байте одного из слов if (Value and $F0F0F0F0)<>0 then result:=result+4; // бит в старшем ниббле одного из байтов if (Value and $CCCCCCCC)<>0 then result:=result+2; //бит в одно из старших битов ниббла if (Value and $AAAAAAAA)<>0 then result:=result+1; //бит на нечетном месте $AA = bin10101010 end; begin l := 0; for i := 0 to 31 do //инициализация, метод de Brujin table[ ( $077CB531 * ( 1 shl i ) ) shr 27 ] := i; t := GetTickCount; for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndexBSR(i); end; Memo1.Lines.Add(Format("BSR %d", [GetTickCount- t])); t := GetTickCount; for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndexDeBruijn(i); end; Memo1.Lines.Add(Format("DeBruijn %d", [GetTickCount- t])); t := GetTickCount; for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndexBinS(i); end; Memo1.Lines.Add(Format("BinSearch %d", [GetTickCount- t])); t := GetTickCount; for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndexSHR(i); end; Memo1.Lines.Add(Format("SHR %d", [GetTickCount- t]));

Athlon 3500+
BSR 1422 DeBruijn 1578 BinSearch 1438 SHR 6422

← →
Dimka Maslov © (2014-10-14 19:40) [29]

Нет x64 под Венду. Не даёт. А если как в спраке сказано, понизить уровень до ворнинга, то говорит, что bsr и eax неизвестные идентификаторы, однако...

← →
MBo © (2014-10-14 19:41) [30]

А вот магические числа deBruijn для 64 бит:
Table[(uint64_t)(val * 0x022fdd63cc95386dull) >> 58];

← →
Rouse_ © (2014-10-14 19:48) [31]

> MBo © (14.10.14 19:39) [28]

Ну как я и говорил изначально - BSR самый шустрый по скорости :)

> Dimka Maslov © (14.10.14 19:40) [29]
> Нет x64 под Венду. Не даёт.

Ты че там такое компиляш?
Давай демку архивом, завтра гляну.

← →
Ega23 © (2014-10-14 19:57) [32]

> Rouse_ © (14.10.14 19:34) [24]
>
> Может и не в тему, но тоже хочу задачку для разминки мозга
> подкинуть.
> Дан ряд чисел от единицы до N (к примеру если N = 6, то
> ряд выглядит как 1,2,3,4,5,6).
> Задача: написать функцию возвращающую сумму всех чисел ряда.
> (При N = 6, результат 21)
> Ограничения - функция не должна использовать цикл или рекурсию.
>

Result := (((N + 1) * N) shr 1);

← →
Dimka Maslov © (2014-10-14 20:00) [33]

#define BIT0 0x01
#define BIT1 0x02
#define BIT2 0x04
#define BIT3 0x08
#define BIT4 0x10
#define BIT5 0x20
#define BIT6 0x40
#define BIT7 0x80

long BitIndex(long N)
{
__asm
{
mov eax, N
bsr eax, eax
}
}

Microsoft Visual Studio 2013 простое консольное приложение 64 бита. Ассемблер более не дозволен.

← →
MBo © (2014-10-14 20:03) [34]

> Microsoft Visual Studio 2013 простое консольное приложение
> 64 бита. Ассемблер более не дозволен.

Интринсики же есть _BitScanReverse64

← →
Юрий Зотов © (2014-10-14 20:04) [35]

А логарифм как, по скорости?

← →
Rouse_ © (2014-10-14 20:10) [36]

> Ega23 © (14.10.14 19:57) [32]

Гаусс? Молоток, зарраза :)

← →
Inovet © (2014-10-14 20:10) [37]

> [24] Rouse_ © (14.10.14 19:34)
> Задача: написать функцию возвращающую сумму всех чисел ряда. При N = 6, результат 21)

Это что ли?
Для нечётных Н*Н/2
для чётных Н*(Н+1)/2

← →
Kerk © (2014-10-14 20:11) [38]

> Дан ряд чисел от единицы до N

https://ru.wikipedia.org/wiki/%C0%F0%E8%F4%EC%E5%F2%E8%F7%E5%F1%EA%E0%FF_%EF%F0%EE%E3%F0%E5%F1%F1%E8%FF#.D0.A1.D1.83.D0.BC.D0.BC.D0.B0_.D0.BF.D0.B5.D1.80.D0.B2.D1.8B.D1.85_.D1.87.D0 .BB.D0.B5.D0.BD.D0.BE.D0.B2_.D0.B0.D1.80.D0.B8.D1.84.D0.BC.D0.B5.D1.82.D0.B8.D1. 87.D0.B5.D1.81.D0.BA.D0.BE.D0.B9_.D0.BF.D1.80.D0.BE.D0.B3.D1.80.D0.B5.D1.81.D1.8 1.D0.B8.D0.B8

?

← →
Rouse_ © (2014-10-14 20:12) [39]

> Inovet © (14.10.14 20:10) [37]

Угу, оно... забыл что вы тут все умные, каюсь. Задачка - так себе :)

← →
Rouse_ © (2014-10-14 20:14) [40]

Есть еще один вариант не методом Гаусса решается, но в принципе - задача решена :)

← →
MBo © (2014-10-14 20:17) [41]

> Юрий Зотов © (14.10.14 20:04) [35]
> А логарифм как, по скорости?

Не быстрый, но и не катастрофа

Result := Round(Log2(DWord(Value)));

DeBruijn 1516 BSR 1437 BinSearch 1344 SHR 6734 Log2 7079

← →
Inovet © (2014-10-14 20:18) [42]

> [38] Kerk © (14.10.14 20:11)

Ну да всегда же делится на 2.

← →
Ega23 © (2014-10-14 20:42) [43]

> Угу, оно... забыл что вы тут все умные, каюсь. Задачка -так себе :)

Тащемта, я подумал что ты как-то хитро стебёшься например.

← →
jack128 © (2014-10-14 21:17) [44]

> function GetIndexBsr(Value: DWORD): Byte; assembler;
> asm
> bsr eax, eax
> end;

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

← →
Dimka Maslov © (2014-10-14 21:36) [45]

> Интринсики же есть _BitScanReverse64

А если я хочу несколько команд? А если надо оптимизировать? А ведь может от этого в Win7 "Оценка продолжительности копирования файлов" в три раза дольше, чем само копирование?

← →
NoUser © (2014-10-14 21:39) [46]

XE2 простое консольное приложение 64 бита ;)

function GetIndexBsr64(Value: NativeUInt): NativeUInt; asm .NOFRAME bsr rcx, rcx mov rax, rcx end;

> jack128 © (14.10.14 21:17) [44]
> тут из-за того, что дельфи вставляет пролог/эпилог - результат
> медленее, чем мог бы быть.

Жек, ты конечно молоток, что асм начал изучать, но не говори глупостей плз :)

> А если я хочу несколько команд? А если надо оптимизировать?

А что этому противоречит? Компилятор VS развернет интринсик в эффективный для целевой платформы код, возможно, в тот же BSR

> MBo ©

немного изменил )

function BitIndexBinS2(Value: Integer): Integer; var a: byte; begin a:=byte((Value and $FFFF0000)<>0); //бит в старшем слове +16 a:=byte((Value and $FF00FF00)<>0) + a + a; //бит в старшем байте одного из слов +8 a:=byte((Value and $F0F0F0F0)<>0) + a + a; //бит в старшем ниббле одного из байтов +4 a:=byte((Value and $CCCCCCCC)<>0) + a + a; //бит в одном из старших битов ниббла +2 a:=byte((Value and $AAAAAAAA)<>0) + a + a; //бит на нечетном месте +1 Result:=a; end;

результат на E-6850:

BSR 312
DeBruijn 328
BinSearch 748
BinSearch2 390
SHR 1779

> Жек, ты конечно молоток, что асм начал изучать, но не говори
> глупостей плз :)

а дело не в асме, а в дельфе. Я действительно тут неправильно понял логику компилятора, когда он вставляет, а когда нет пролог в асм код.

> XE2 простое консольное приложение 64 бита ;)

У меня Visual C++ же

> А что этому противоречит?

Правилу не изобретать лишних сущностей. Ведь кроме BSR существует достаточное количество других инструкций, при последовательном вызове которых вместо простого и понятного кода получится каша из кучи вызовов. Ну а кроме того, нет ничего сложного в портировании команд ассемблера, а не вызовов функций. В добавок, у меня одна платформа и я не собираюсь переносить свой проект на другую. Так что, на мой взгляд, замена прямого ассемблера кривым - очередной шаг в неправильную сторону.

Ну а кроме того, компилятор, который на функцию
long long Inc(long long& N) { return ++N; }

генерирует код
mov qword ptr [rsp+8],rcx push rdi mov rax,qword ptr [N] mov rax,qword ptr [rax] inc rax mov rcx,qword ptr [N] mov qword ptr [rcx],rax mov rax,qword ptr [N] mov rax,qword ptr [rax] pop rdi ret

вместо казалось бы
mov rax, qword ptr [ecx] inc rax mov qword ptr [ecx], eax ret

На мой взгляд далёк от оптимального

Конечно далек, ибо оптимальный это: lea rcx, [rcx + 1] :)

А вот и нет:

function _Inc(var N: Integer): Integer; asm lea eax, [eax+1] end;
выдаёт полную чушь
N как был, так и остаётся, а возвращается его адрес, вместо значения

Да, ошибся, реф не увидел...

> Ну а кроме того, компилятор, который на функцию

Это в релизе ?? У мя на 2013 в релизе такой код генерится

int _tmain(int argc, _TCHAR* argv[]) { __debugbreak(); long long n; std::cin >> n; Inc(n); // !!!!!!!!!!!!!!!!!!!!!!!!!!!! твоя функция std::cout << n; return 0; }

int _tmain(int argc, _TCHAR* argv[]) { 000000013FF31270 sub rsp,38h 000000013FF31274 mov rax,qword ptr [__security_cookie (013FF35000h)] 000000013FF3127B xor rax,rsp 000000013FF3127E mov qword ptr [rsp+28h],rax __debugbreak(); 000000013FF31283 int 3 long long n; std::cin >> n; 000000013FF31284 mov rcx,qword ptr [__imp_std::cin (013FF33078h)] 000000013FF3128B lea rdx,[n] 000000013FF31290 call qword ptr [__imp_std::basic_istream<char,std::char_traits<char> >::operator>> (013FF33050h)] Inc(n); 000000013FF31296 mov rdx,qword ptr [n] /// !!!!!!!!!!!!!!!!!!!!!!!!!!!! грузим из памяти в регистр std::cout << n; 000000013FF3129B mov rcx,qword ptr [__imp_std::cout (013FF33070h)] Inc(n); 000000013FF312A2 inc rdx /// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! увеличиваем на единичку 000000013FF312A5 mov qword ptr [n],rdx // пишем обратно в память std::cout << n; 000000013FF312AA call qword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (013FF33048h)] return 0; 000000013FF312B0 xor eax,eax }

> У меня Visual C++ же
Ну так dll"кой на крайняк ), а то просто слинковать с внешним *.obj, или это тоже в V$2013 запретили?

>Sha © (14.10.14 22:48) [51]
Сильно зависит от процессора и режима сборки.
В дебаг-режиме твой код приводит после test к setnz вместо условного перехода jz, но на моей машине это оказывается хуже исходного варианта. А в релизе - не знаю, что получается, но лучше ;)

i5-4670 XE3 Debug BSR 343 DeBruijn 390 BinSearch 546 BinSearch2 827 SHR 3229 Log2 3603 Release BSR 203 DeBruijn 187 BinSearch 374 BinSearch2 312 SHR 812 Log2 3354

MBo © (15.10.14 09:24) [60]

у меня D7 не вставляет ничего лишнего, работает прямо с байтами, использует только операции setnz и add

> работает прямо с байтами, использует только операции setnz и add
Да, так и есть (в debug, в release я не знаю, как проконтролировать)

Search2
Unit1.pas.76: a:=byte((Value and $FF00FF00)<>0) + a + a; //бит в старшем байте одного из слов +8 005AE6DE F745FC00FF00FF test [ebp-$04],$ff00ff00 005AE6E5 0F95C0 setnz al 005AE6E8 0245F7 add al,[ebp-$09] 005AE6EB 0045F7 add [ebp-$09],al

Search
Unit1.pas.65: if (Value and $FF00FF00)<>0 then result:=result+8; // бит в старшем байте одного из слов 005AE68B F745FC00FF00FF test [ebp-$04],$ff00ff00 005AE692 7404 jz $005ae698 005AE694 8345F808 add dword ptr [ebp-$08],$08

Ужас эти новые версии.
В D7 все действия только с регистрами.

Если нет доступа к встроенному ассеблеру, то первое, что приходит в голову, це

const int magic[64] = { 0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4, 62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5, 63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11, 46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6 }; return magic[(0x03f79d71b4cb0a89ull * value) >> 58];

Вот с логарифмом версия

{ union { double d; struct { unsigned int mantissal : 32; unsigned int mantissah : 20; unsigned int exponent : 11; unsigned int sign : 1; }; } ud; ud.d = (double)(bb); return ud.exponent - 1023; }

Еще вариантьі тут
https://chessprogramming.wikispaces.com/BitScan

> jack128 © (15.10.14 00:08) [58]

В релизе. И вообще пример не показательный. И вообще когда дельфийский отладчик заходит в сишный код, становится страшно от того, что там понапихано, а главное зачем. Я вот свой старый проект, который до сих пор жил в 2005 студии собрал в 2013. Мало того, он стал в 1.5 раза больше, так ещё и заметно медленнее на больших задачах.

> NoUser © (15.10.14 00:13) [59]

На самый крайняк можно вспомнить TurboPascal3.0 в которым не было ассемблера, но можно было напрямую в кодах писать.

Задачка::Проверка бита Найти похожие ветки