• + 0 comments

    Python 3

    TL;DR

    def bitwiseAnd(N, K):
        while K > 0:
            K -= 1
            tested = K+(1<<list(reversed(f'{K:b}')).index('0')) if "0" in f"{K:b}" else K+(1<<len(f'{K:b}'))
            if tested <= N :
                return K
    

    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.

    Happy pythoning!

    🦁