We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Pros: get solution in max 2 iterations (if I'm not wrong)
In details
As example: given K=180. (K-1) = 179 = b10110011
Find int X, that X & 179 = 179:
K-1= 179: b10110011
X1 = 183: b10110111
X2 = 191: b10111111
X3 = 255: b11111111
and
X4 = 511: b111111111 (note additional leading 1)
0 is inside binary (K-1). Replace 0 by 1. In most cases binary representation of K-1 has few 0 inside, like in our example: (K-1) = 179 is b10110011. In such cases take 1st candidate 183 b10110111. Test if 183 is less or equal N. If True, then 179 is the answer. If False, no need to test other candidates (191,255,511), because they are defenetly greater that N.
No 0 is inside binary (K-1). Add leading 1 to binary representation. This is edge case, when binary representation of K-1 is all 1 only. Exampe: K=256, K-1=255: b11111111 (8x1). In this case you need to test if 511: b111111111 (9x1) is less or equal N. If True then 255 is the answer.
If above test yield False, reduce N by 1 and repeat the test.
Day 29: Bitwise AND
You are viewing a single comment's thread. Return to all comments →
Python 3
TL;DR
Pros: get solution in max 2 iterations (if I'm not wrong)
In details
As example: given K=180. (K-1) = 179 = b
10110011
Find int
X
, thatX & 179 = 179
:10110011
10110111
10111111
11111111
111111111
(note additional leading1
)0 is inside binary (K-1). Replace 0 by 1. In most cases binary representation of
K-1
has few0
inside, like in our example: (K-1) = 179 is b10110011
. In such cases take 1st candidate 183 b10110111
. Test if 183 is less or equalN
. If True, then 179 is the answer. If False, no need to test other candidates (191,255,511), because they are defenetly greater thatN
.No 0 is inside binary (K-1). Add leading 1 to binary representation. This is edge case, when binary representation of
K-1
is all1
only. Exampe: K=256, K-1=255: b11111111
(8x1). In this case you need to test if 511: b111111111
(9x1) is less or equalN
. If True then 255 is the answer.If above test yield False, reduce
N
by 1 and repeat the test.Happy pythoning!
🦁