#include <iostream>
using namespace std;
int msb(int x) {
union { double a; int b[2]; };
a = x;
return (b[1] >> 20) - 1023;
}
int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - ((unsigned)i >> 1);
}
int main() {
double t1, t2;
const int lim = 200 * 1000 * 1000;
{
t1 = clock();
for (int i = 0; i < lim; i++) {
int t = msb(i);
if (t == -42) return 1;
}
t2 = clock();
cout << (t2 - t1) / 1000.0 << endl;
}
{
t1 = clock();
for (int i = 0; i < lim; i++) {
int t = highestOneBit(i);
if (t == -42) return 1;
}
t2 = clock();
cout << (t2 - t1) / 1000.0 << endl;
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1zYihpbnQgeCkgewogICAgdW5pb24geyBkb3VibGUgYTsgaW50IGJbMl07IH07CiAgICBhID0geDsKICAgIHJldHVybiAoYlsxXSA+PiAyMCkgLSAxMDIzOwp9CgppbnQgaGlnaGVzdE9uZUJpdChpbnQgaSkgewogICAgLy8gSEQsIEZpZ3VyZSAzLTEKICAgIGkgfD0gKGkgPj4gIDEpOwogICAgaSB8PSAoaSA+PiAgMik7CiAgICBpIHw9IChpID4+ICA0KTsKICAgIGkgfD0gKGkgPj4gIDgpOwogICAgaSB8PSAoaSA+PiAxNik7CiAgICByZXR1cm4gaSAtICgodW5zaWduZWQpaSA+PiAxKTsKfQoKaW50IG1haW4oKSB7CiAgICBkb3VibGUgdDEsIHQyOwogICAgY29uc3QgaW50IGxpbSA9IDIwMCAqIDEwMDAgKiAxMDAwOwogICAgewogICAgCXQxID0gY2xvY2soKTsKICAgIAlmb3IgKGludCBpID0gMDsgaSA8IGxpbTsgaSsrKSB7CgkJCWludCB0ID0gbXNiKGkpOwoJCQlpZiAodCA9PSAtNDIpIHJldHVybiAxOwoJCX0KCQl0MiA9IGNsb2NrKCk7CgkJY291dCA8PCAodDIgLSB0MSkgLyAxMDAwLjAgPDwgZW5kbDsKICAgIH0KICAgIHsKICAgIAl0MSA9IGNsb2NrKCk7CiAgICAJZm9yIChpbnQgaSA9IDA7IGkgPCBsaW07IGkrKykgewoJCQlpbnQgdCA9IGhpZ2hlc3RPbmVCaXQoaSk7CgkJCWlmICh0ID09IC00MikgcmV0dXJuIDE7CgkJfQoJCXQyID0gY2xvY2soKTsKCQljb3V0IDw8ICh0MiAtIHQxKSAvIDEwMDAuMCA8PCBlbmRsOwogICAgfQp9Cg==