시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 563 129 94 31.864%

문제

두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.

즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.

\[\sum_{x=A}^{B}{f(x)}\]

입력

첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 1016)

출력

1의 개수를 세어 출력한다.

예제 입력 1

2 12

예제 출력 1

21
W3sicHJvYmxlbV9pZCI6Ijk1MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIxXHVjNzU4IFx1YWMxY1x1YzIxOCBcdWMxMzhcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjQ1MCBcdWM3OTBcdWM1ZjBcdWMyMTggQSwgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBBJm5ic3A7JmxlOyB4Jm5ic3A7JmxlOyBCXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgeFx1YzVkMCBcdWIzMDBcdWQ1NzQgeFx1Yjk3YyZuYnNwO1x1Yzc3NFx1YzljNFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1ODhcdWM3NDQgXHViNTRjIDFcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjOTg5LCBmKHgpID0geFx1Yjk3YyBcdWM3NzRcdWM5YzRcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0IFx1ZDU4OFx1Yzc0NCBcdWI1NGMgMVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI3N2NcdWFjZTAgXHVjODE1XHVjNzU4XHVkNTU4XHVhY2UwLCBcdWM1NDRcdWI3OTggXHVjMmRkXHVjNzU4IFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlxcW1xcc3VtX3t4PUF9XntCfXtmKHgpfVxcXTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4IEEsIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZuYnNwOyZsZTsgQSZuYnNwOyZsZTsgQiZuYnNwOyZsZTsgMTA8c3VwPjE2PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4xXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxMzhcdWM1YjQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk1MjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb3VudGluZyBvbmVzIiwiZGVzY3JpcHRpb24iOiI8cD5DYXJsIGlzIHJpZ2h0IG5vdyB0aGUgaGFwcGllc3QgY2hpbGQgaW4gdGhlIHdvcmxkOiBoZSBoYXMganVzdCBsZWFybmVkIHRoaXMgbW9ybmluZyB3aGF0IHRoZSBiaW5hcnkgJm5ic3A7c3lzdGVtIGlzLiBIZSBsZWFybmVkLCBmb3IgaW5zdGFuY2UsIHRoYXQgdGhlIGJpbmFyeSByZXByZXNlbnRhdGlvbiBvZiBhIHBvc2l0aXZlIGludGVnZXIgayBpcyBhIHN0cmluZyBhPHN1Yj5uPFwvc3ViPmE8c3ViPm4mbWludXM7MTxcL3N1Yj4gJm1pZGRvdDsgJm1pZGRvdDsgJm1pZGRvdDsgYTxzdWI+MTxcL3N1Yj5hPHN1Yj4wPFwvc3ViPiB3aGVyZSBlYWNoIGFpIGlzIGEgYmluYXJ5IGRpZ2l0IDAgb3IgMSwgc3RhcnRpbmcgd2l0aCBhPHN1Yj5uPFwvc3ViPiA9IDEsIGFuZCBzdWNoIHRoYXQgXFwoayA9IFxcc3VtX3tpPTB9IF57bn0mbmJzcDt7YV9pIFxcdGltZXMmbmJzcDsyXml9XFwpLiBJdCBpcyByZWFsbHkgbmljZSB0byBzZWUgaGltIHR1cm5pbmcgZGVjaW1hbCBudW1iZXJzIGludG8gYmluYXJ5IG51bWJlcnMsIGFuZCB0aGVuIGFkZGluZyBhbmQgZXZlbiBtdWx0aXBseWluZyB0aGVtLjxcL3A+XHJcblxyXG48cD5DYWVzYXIgaXMgQ2FybCZyc3F1bztzIG9sZGVyIGJyb3RoZXIsIGFuZCBoZSBqdXN0IGNhbiZyc3F1bzt0IHN0YW5kIHRvIHNlZSBoaXMgbGl0dGxlIGJyb3RoZXIgc28gaGFwcHkuIFNvIGhlIGhhcyBwcmVwYXJlZCBhIGNoYWxsZW5nZTogJmxkcXVvO0xvb2sgQ2FybCwgSSBoYXZlIGFuIGVhc3kgcXVlc3Rpb24gZm9yIHlvdTogSSB3aWxsIGdpdmUgeW91IHR3byBpbnRlZ2VycyBBIGFuZCBCLCBhbmQgeW91IGhhdmUgdG8gdGVsbCBtZSBob3cgbWFueSAxJnJzcXVvO3MgdGhlcmUgYXJlIGluIHRoZSBiaW5hcnkgcmVwcmVzZW50YXRpb24gb2YgYWxsIHRoZSBpbnRlZ2VycyBmcm9tIEEgdG8gQiwgaW5jbHVzaXZlLiBHZXQgcmVhZHkmcmRxdW87LiBDYXJsIGFncmVlZCB0byB0aGUgY2hhbGxlbmdlLiBBZnRlciBhIGZldyBtaW51dGVzLCBoZSBjYW1lIGJhY2sgd2l0aCBhIGxpc3Qgb2YgdGhlIGJpbmFyeSByZXByZXNlbnRhdGlvbiBvZiBhbGwgdGhlIGludGVnZXJzIGZyb20gMSB0byAxMDAuICZsZHF1bztDYWVzYXIsIEkmcnNxdW87bSByZWFkeSZyZHF1bzsuIENhZXNhciBzbWlsZWQgYW5kIHNhaWQ6ICZsZHF1bztXZWxsLCBsZXQgbWUgc2VlLCBJIGNob29zZSBBID0gMTA8c3VwPjE1PFwvc3VwPiBhbmQgQiA9IDEwPHN1cD4xNjxcL3N1cD4uIFlvdXIgbGlzdCB3aWxsIG5vdCBiZSB1c2VmdWwmcmRxdW87LjxcL3A+XHJcblxyXG48cD5DYXJsIGhhdGVzIGxvb3NpbmcgdG8gaGlzIGJyb3RoZXIgc28gaGUgbmVlZHMgYSBiZXR0ZXIgc29sdXRpb24gZmFzdC4gQ2FuIHlvdSBoZWxwIGhpbT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgdGhhdCBjb250YWlucyB0d28gaW50ZWdlcnMgQSBhbmQgQiAoMSAmbGU7IEEgJmxlOyBCICZsZTsgMTA8c3VwPjE2PFwvc3VwPikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgbGluZSB3aXRoIGFuIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSB0b3RhbCBudW1iZXIgb2YgZGlnaXRzIDEgaW4gdGhlIGJpbmFyeSByZXByZXNlbnRhdGlvbiBvZiBhbGwgdGhlIGludGVnZXJzIGZyb20gQSB0byBCLCBpbmNsdXNpdmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d