Проверете дали е зададен само един бит в рамките на цяло число (каквато и да е неговата позиция)

Съхранявам флагове, използвайки битове в рамките на 64-битово цяло число.
Искам да знам дали има един бит, зададен независимо от позицията в рамките на 64-битовото цяло число (т.е. не ме интересува позицията на всеки конкретен бит).

boolean isOneSingleBitSet (long integer64)
{
   return ....;
}

Мога да преброя броя на битовете с помощта на Bit Twiddling Hacks (от Шон Eron Anderson), но се чудя кой е най-ефективният начин просто да открия дали е зададен един единствен бит...

Намерих някои други свързани въпроси:

както и някои страници в Уикипедия:

NB: моето приложение е на java, но съм любопитен за оптимизации, използващи други езици...

РЕДАКТИРАНЕ: Lưu Vĩnh Phúc посочи, че първата ми връзка във въпроса ми вече е получила отговор: вижте раздела Определяне дали цяло число е степен на 2 в Bit Twiddling Hacks(от Шон Ерон Андерсън). Не разбрах, че един бит е същият като степен на две.


java binary bit-manipulation bit bitwise-operators
person oHo    schedule 16.11.2012    source източник
comment
За Java бих обмислил използването на клас BitSet за тази цел, който поддържа удобен метод isEmpty(), както и много други, което прави битовите флагове много по-лесни за използване.   -  person maximdim    schedule 16.11.2012
comment
това вече е в Bit Twiddling Hacks, свързани по-горе: Определяне дали цяло число е степен на 2   -  person phuclv    schedule 04.10.2015
comment
о! Благодаря ви :-) Актуализирам въпроса си :-) Наздраве   -  person oHo    schedule 05.10.2015
comment
Това отговаря ли на въпроса ви? Как да проверя дали дадено число е степен на 2   -  person Tsyvarev    schedule 09.04.2020

Отговори (6)


arrow_upward
23
arrow_downward

Ако буквално искате да проверите дали е зададен един-единствен бит, тогава по същество проверявате дали числото е степен на 2. За да направите това, можете да направите:

if ((number & (number-1)) == 0) ...

Това също ще брои 0 като степен на 2, така че трябва да проверите дали числото не е 0, ако това е важно. Така че след това:

if (number != 0 && (number & (number-1)) == 0) ...
person Neil Coffey    schedule 16.11.2012
comment
Съжалявам, но тествах отговора ви, имам тези резултати: 0-›false (ок) ; 1-›true (добре) ; 2-›false (KO) ; 3-›false (добре) ; 4-›false (KO) 5-›false (добре) ... Моля, бихте ли го проверили и от ваша страна? - person oHo; 16.11.2012
comment
Разгледайте втората версия, където съм посочил как ще изглежда с проверката за != 0. Наистина е добре, доколкото виждам. - person Neil Coffey; 16.11.2012
comment
Благодаря ви за вашата редакция, но вашият първи ред if ((number & (number-1)) == 0) ... не проверява дали number е степен на 2, както можете да видите в резултатите от моя тест (вижте предишния ми коментар). За да проверите дали numberе степен на две, можете да направите: if (number && !(number & (number - 1)) ... (моля, приемете моята редакция във вашия отговор) - person oHo; 16.11.2012
comment
Не в Java не можете. В C редът, който сте написали, ще бъде по същество еквивалентен на това, което съм написал. Ако искате отговор, подходящ за C, а не за Java, моля, коригирайте и маркирайте отново въпроса си съответно. - person Neil Coffey; 16.11.2012
comment
Моите извинения, първият ви ред е ОК (с изключение на нула, както казвате). И вторият ти ред е перфектен :-) Но аз наградих @JanDvorak, защото той беше първият, който даде правилния отговор. Благодаря ви много за помощта =› +1 - person oHo; 19.11.2012
comment
Добре, въпреки че казах устно, че трябва да направите нулевата проверка: наистина ли не успяхте да превърнете това в код?? - person Neil Coffey; 19.11.2012

arrow_upward
16
arrow_downward

(използвайки x като аргумент)

Откриването дали е зададен поне един бит е лесно:

return x!=0;

По същия начин откриването дали първи бит (вторият най-нисък бит) е зададен е лесно:

return (x&2)!=0;

Задава се точно един бит, ако е степен на две. Това работи:

return x!=0 && (x & (x-1))==0;
person John Dvorak    schedule 16.11.2012
comment
Има ли някакъв начин да се провери кой бит е включен? (до дънер) Страхотен трик между другото - person hl3mukkel; 21.03.2014
comment
@hl3mukkel можете да използвате итерирано деление (което е просто начин за изчисляване на цял логаритъм). Ако търсите нещо по-бързо, проверете stackoverflow.com/q/14429661/499214. Използването на логаритъм определено е по-разбираемо, подлежи на проблеми със закръгляването. - person John Dvorak; 22.03.2014
comment
Благодаря! Намерих връзката за ефективен и чист подход. - person hl3mukkel; 22.03.2014

arrow_upward
3
arrow_downward

Класът обвивка java.lang.Long има статична функция bitCount(), която връща броя битове в дълго (64-битово int):

boolean isSingleBitSet(long l)
{
     return Long.bitCount(l) == 1;
}

Имайте предвид, че ints са 32-битови в java.

person ApproachingDarknessFish    schedule 16.11.2012
comment
Промяна на условието на ==1, това ще работи, но почти сигурно не е най-ефективният начин за откриване на един бит, строго погледнато. - person Neil Coffey; 16.11.2012
comment
Знаете ли режийните разходи на този метод? Това със сигурност е най-четимото решение, дори и да не е най-бързото. - person John Dvorak; 16.11.2012
comment
Както е сега (>0), това ще провери дали числото е различно от нула (благодаря на @NeilCoffey, че забеляза). - person John Dvorak; 16.11.2012
comment
+1 за това читаво решение. Има ли функция за проверка дали цялото число е степен на две? - person oHo; 16.11.2012
comment
Ян - Предполагам, само от броя на операциите, че ще бъде основно няколко пъти по-бавно от обичайния метод, който споменавам в отговора си. Що се отнася до четливостта, можете да обвиете всяка реализация, която искате, в метод, наречен isSingleBitSet() -- не съм сигурен каква е разликата от тази гледна точка... - person Neil Coffey; 16.11.2012
comment
... или казано по друг начин, всъщност погледнете изходния код на Long.bitCount() и ми кажете колко четлив е според вас...! - person Neil Coffey; 16.11.2012
comment
@olibre Всички степени на две с изключение на 0 имат точно един бит - въпросите са едни и същи! - person ApproachingDarknessFish; 17.11.2012

arrow_upward
2
arrow_downward

нека приемем, че X е 64-битов интер, пълен с 0, с изключение на този, който търсите;

  return ((64bitinteger&X)==X)
person Ercan    schedule 16.11.2012
comment
връща истина, когато 64bitinteger = 0 :-( - person oHo; 16.11.2012
comment
какво е X в отговора ти? Същото като 64bitinteger? - person oHo; 16.11.2012
comment
1010101, ако искате да проверите дали 3-тият бит е 1 1010101 & 0010000 е равно на 0010000 в този пример X=0010000 - person Ercan; 16.11.2012
comment
благодаря за отговора, но търся най-ефективния начин да разбера дали има зададен един бит на която и да е позиция... - person oHo; 17.11.2012

arrow_upward
1
arrow_downward

Ако приемем, че вече имате ефективна - или хардуерна - реализация на ffs() - намери първия набор - можете да действате както следва:

bool isOneSingleBitSet (long integer64)
{
   return (integer64 >> ffs(integer64)) == 0;
}

Функцията ffs() може вече да е налична или може да искате да видите собствената си връзка по-горе

person Ali    schedule 16.11.2012
comment
ffs() наличен ли е в java? - person oHo; 16.11.2012
comment
+1 вашият отговор е валиден :-), но е тестван с помощта на GCC __builtin_ffs(). Моля, кажете ми дали ffs() е наличен в java... - person oHo; 16.11.2012
comment
Аз не съм Java разработчик! Просто се интересувам от въпроса ви - person Ali; 16.11.2012

arrow_upward
0
arrow_downward

Изглежда, че можете да направите побитово И с long представяне на единичния бит, който искате да проверите. Например, за да проверите LSB

return(   (integer64 & 1L)!=0  );

Или да проверите 4-тия бит отдясно

return(   (integer64 & 8L)!=0  );
person Pursuit    schedule 16.11.2012
comment
добре... но как да проверите дали има един единствен бит? Проверявате ли всеки 64 бита? - person oHo; 16.11.2012
comment
Използвайки метода в този отговор, да, но не бих го препоръчал. Разбрах първоначалния въпрос като проверка на конкретен бит, а не проверка за всеки отделен бит, както е предвидено. Въпросът, както възнамерявахте, е по-интересен и добре отговорен от Нийл Кофи и Ян Дворак. - person Pursuit; 16.11.2012
comment
Благодаря @Pursuit. Ще подобря малко въпроса си, за да е по-разбираем ;-) - person oHo; 17.11.2012