[WI] test of de bit aanstaat in decimale vorm

[bulbanos]

hey,

welke methode is het snelst om te testen of een bit op positie n aanstaat als je enkel de decimale waarde weet? Dus geen omzettingen naar binair mogelijk.
bv: we willen weten of bit 7 nul of één is in de binaire representatie van 658. (Nee: 10010010)

[ILUsion]

Als je het moet implementeren in een computer, maakt het getallenstelsel niet uit, vermits dat toch al binair is. (Vermits ik de indruk heb dat veel mensen bij het programmeren vastlopen als er meerdere talstelsels door elkaar gebruikt worden: 658 = 00001010010010₂ =0292₁₆ = ... en voor de computer kost het enkel moeite om die om te zetten naar decimaal (en een verwaarloosbaar beetje voor hexadecimaal); al moet je daar niet op kijken in 99.9% van de gevallen). Dus ik zeg het er gewoon maar bij voordat je al die moeite doet: op een computer kan je dat veel makkelijker doen als volgt (en ook veel sneller dan wat je decimaal zou doen):

A = 658;    % getal
B = 2^6;    % bit die je wilt
C = A & B;  % bitwise AND
if C == B   % de uitkomst is ofwel 64 ofwel 0 (als je een enkele bit zet in B)
    disp('bitje is gezet');
else
    disp('bitje is niet gezet');
end;

Als je het manueel moet doen, zou ik iets doen van de volgende aard:
Ik zal jouw voorbeeld 658 nemen en dezelfde bit: 00001010010010₂

Ik zou beginnen met te bepalen wat de waarde van het getal 1000000₂ is, dat is 64 (dus als je bit op 1 staat en al de rest nul, heb je 64).

We weten dus ook dat alle bit daarboven (in het rood weergegeven) onnodig zijn, dat zijn stricte veelvouden van 128 (= 2 * 64); wegsmijten die handel:
658 - N * 128 = K
hierin is N een natuurlijk getal en zo groot mogelijk waarbij de uitkomst K positief blijft. Simpel gezegd kan je gewoon enkele keren 128 aftrekken (5 in dit geval, zoals je ook kan zien in de binaire voorstelling) en je bekomt een uitkomst: K = 18.

Daar zie je gewoon op het zicht al dat daar geen 64-bitje inzit. Stel dat je iets 127 > uitkomt > 63, zit je bit er wel in.