ほぼ日刊競プロ ABC269 C - Submask

C - Submask

問題文
非負整数 N が与えられるので、以下の条件を満たす非負整数 x を昇順に全て出力してください。
x を 2 進数として表記した時に 1 となる位の集合が、 N を 2 進数として表記した時に 1 となる位の集合の部分集合となる。
すなわち、全ての非負整数 k について、「 x の 2^kの位が 1 ならば、 N の 2^kの位は 1 」が成り立つ。

考えたこと

おそらくbit全探索と＆演算を使えば解けそうだと考えたが，時間切れでした．
この問題は灰らしいです．．．挫けそうです．
以下のように後で考えました．
2進数に直して，1が立つ位置を覚えて，2**（１が立つ回数）までbit全探索する．
シフトビットしていき&１が成り立てば，その位置を覚える．

2進数に直した桁数までに，上記の位置があれば，１を立てる．そうでなければ０
最後に，10進数に直してソートしてあげれば終わり．
本番でできる気がしない．．．

N= int(input())
temp =str(bin(N))
index = []
#print (temp)
length = []
for i in range(len(temp)):
   #print (temp[i])
   if temp[i]=="1":
       index.append(i)
#print (index)
ans = []
for i in range(2**len(index)):
   bag = []
   for j in range(len(index)):
       if i>>j &1 ==1:
           bag.append(index[j])
   if len(bag)==0:
       ans.append(0)
   else:
       A ='0b'
       for k in range(len(temp)):
           if k in bag:
               A+="1" 
           else:
               A+='0'
       
       ans.append(int(A,2))
ans = sorted(ans)
for i in ans:
   print (i)