How to calculate all number from 1 to $N$ whose bitwise AND with $X$ is same to the number itself?

80 Views Asked by At

Let's say $X = 6$ and $N = 100$ so the number$(P)$ from $1$ to $100$ when bitwise AND with $6$ gives same number$(P)$ are : $$0,2,4,6$$

for $X = 7$

$$0 1 2 3 4 5 6 7$$

I couldn't find better approach then brute forcing. I have also calculated all the number up to $17$ hoping to find some relation but don't seem to find one.

$$1: 0,1$$

$$2: 0,2$$

$$3: 0,1,2,3$$

$$4: 0,4$$

$$5: 0,1,4,5$$

$$6: 0,2,4,6$$

$$7: 0,1,2,3,4,5,6,7$$

$$8: 0,8$$

$$9: 0,1,8,9$$

$$10: 0,2,8,10$$

$$11: 0,1,2,3,8,9,10,11$$

$$12: 0,4,8,12$$

$$13: 0,1,4,5,6,8,10,12,14$$

$$14: 0,2,4,6,8,10,12,14$$

$$15: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15$$

$$16: 0,16$$

$$17: 0,1,16,17$$

Also, $X$ can be greater then $N$.

How to approach this problem?