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`

, that`X & 179 = 179`

:`10110011`

`10110111`

`10111111`

`11111111`

`111111111`

(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 b`10110011`

. In such cases take 1st candidate 183 b`10110111`

. Test if 183 is less or equal`N`

. IfTrue, then 179 is the answer. IfFalse, 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 isedge case, when binary representation of`K-1`

is all`1`

only. Exampe: K=256, K-1=255: b`11111111`

(8x1). In this case you need to test if 511: b`111111111`

(9x1) is less or equal`N`

. IfTruethen 255 is the answer.If above test yield False, reduce

`N`

by 1 and repeat the test.Happy pythoning!

🦁