<p>what I'm after is something I can feed a number into and it will return the highest order bit.  I'm sure there's a simple way.  Below is an example output (left is the input)</p>

<pre>1 -> 1
2 -> 2
3 -> 2
4 -> 4
5 -> 4
6 -> 4
7 -> 4
8 -> 8
9 -> 8
...
63 -> 32</pre>

[{'answer_id': 53174, 'author': 'nlucaroni', 'author_id': 157, 'author_profile': 'https://Stackoverflow.com/users/157', 'pm_score': 3, 'selected': False, 'text': '<p>Continually remove the low order bit comes to mind...</p>\n\n<pre><code>int highest_order_bit( int x )\n{\n    int y = x;\n    do { \n        x = y;\n        y = x &amp; (x-1); //remove low order bit\n    }\n    while( y != 0 );\n    return x;\n}\n</code></pre>\n'}, {'answer_id': 53175, 'author': 'Kyle Cronin', 'author_id': 658, 'author_profile': 'https://Stackoverflow.com/users/658', 'pm_score': 6, 'selected': True, 'text': '<p>This should do the trick.</p>\n\n<pre><code>int hob (int num)\n{\n    if (!num)\n        return 0;\n\n    int ret = 1;\n\n    while (num &gt;&gt;= 1)\n        ret &lt;&lt;= 1;\n\n    return ret;\n}\n</code></pre>\n\n<p>hob(1234) returns 1024<br>\nhob(1024) returns 1024<br>\nhob(1023) returns 512</p>\n'}, {'answer_id': 53184, 'author': 'erickson', 'author_id': 3474, 'author_profile': 'https://Stackoverflow.com/users/3474', 'pm_score': 7, 'selected': False, 'text': "<p>From Hacker's Delight:</p>\n\n<pre><code>int hibit(unsigned int n) {\n    n |= (n &gt;&gt;  1);\n    n |= (n &gt;&gt;  2);\n    n |= (n &gt;&gt;  4);\n    n |= (n &gt;&gt;  8);\n    n |= (n &gt;&gt; 16);\n    return n - (n &gt;&gt; 1);\n}\n</code></pre>\n\n<p>This version is for 32-bit ints, but the logic can be extended for 64-bits or higher.</p>\n"}, {'answer_id': 53229, 'author': 'theorbtwo', 'author_id': 4839, 'author_profile': 'https://Stackoverflow.com/users/4839', 'pm_score': 3, 'selected': False, 'text': '<p>The linux kernel has a number of handy bitops like this, coded in the most efficient way for a number of architectures.  You can find generic versions in <a href="http://lxr.linux.no/linux+v2.6.26.5/include/asm-generic/bitops/fls.h" rel="nofollow noreferrer">include/asm-generic/bitops/fls.h</a> (and friends), but see also <a href="http://lxr.linux.no/linux+v2.6.26.5/include/asm-x86/bitops.h" rel="nofollow noreferrer">include/asm-x86/bitops.h</a> for a definition using inline assembly if speed is of the essence, and portability is not.</p>\n'}, {'answer_id': 53298, 'author': 'Ben Lever', 'author_id': 2045, 'author_profile': 'https://Stackoverflow.com/users/2045', 'pm_score': 2, 'selected': False, 'text': '<p>A fast way to do this is via a look-up table. For a 32-bit input, and an 8-bit look-up table, in only requires 4 iterations:</p>\n\n<pre><code>int highest_order_bit(int x)\n{\n    static const int msb_lut[256] =\n        {\n            0, 0, 1, 1, 2, 2, 2, 2, // 0000_0000 - 0000_0111\n            3, 3, 3, 3, 3, 3, 3, 3, // 0000_1000 - 0000_1111\n            4, 4, 4, 4, 4, 4, 4, 4, // 0001_0000 - 0001_0111\n            4, 4, 4, 4, 4, 4, 4, 4, // 0001_1000 - 0001_1111\n            5, 5, 5, 5, 5, 5, 5, 5, // 0010_0000 - 0010_0111\n            5, 5, 5, 5, 5, 5, 5, 5, // 0010_1000 - 0010_1111\n            5, 5, 5, 5, 5, 5, 5, 5, // 0011_0000 - 0011_0111\n            5, 5, 5, 5, 5, 5, 5, 5, // 0011_1000 - 0011_1111\n\n            6, 6, 6, 6, 6, 6, 6, 6, // 0100_0000 - 0100_0111\n            6, 6, 6, 6, 6, 6, 6, 6, // 0100_1000 - 0100_1111\n            6, 6, 6, 6, 6, 6, 6, 6, // 0101_0000 - 0101_0111\n            6, 6, 6, 6, 6, 6, 6, 6, // 0101_1000 - 0101_1111\n            6, 6, 6, 6, 6, 6, 6, 6, // 0110_0000 - 0110_0111\n            6, 6, 6, 6, 6, 6, 6, 6, // 0110_1000 - 0110_1111\n            6, 6, 6, 6, 6, 6, 6, 6, // 0111_0000 - 0111_0111\n            6, 6, 6, 6, 6, 6, 6, 6, // 0111_1000 - 0111_1111\n\n            7, 7, 7, 7, 7, 7, 7, 7, // 1000_0000 - 1000_0111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1000_1000 - 1000_1111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1001_0000 - 1001_0111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1001_1000 - 1001_1111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1010_0000 - 1010_0111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1010_1000 - 1010_1111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1011_0000 - 1011_0111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1011_1000 - 1011_1111\n\n            7, 7, 7, 7, 7, 7, 7, 7, // 1100_0000 - 1100_0111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1100_1000 - 1100_1111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1101_0000 - 1101_0111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1101_1000 - 1101_1111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1110_0000 - 1110_0111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1110_1000 - 1110_1111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1111_0000 - 1111_0111\n            7, 7, 7, 7, 7, 7, 7, 7, // 1111_1000 - 1111_1111\n        };\n\n    int byte;\n    int byte_cnt;\n\n    for (byte_cnt = 3; byte_cnt &gt;= 0; byte_cnt--)\n    {\n        byte = (x &gt;&gt; (byte_cnt * 8)) &amp; 0xff;\n        if (byte != 0)\n        {\n            return msb_lut[byte] + (byte_cnt * 8);\n        }\n    }\n\n    return -1;\n}\n</code></pre>\n'}, {'answer_id': 53509, 'author': 'dmityugov', 'author_id': 3232, 'author_profile': 'https://Stackoverflow.com/users/3232', 'pm_score': 5, 'selected': False, 'text': '<p>like obfuscated code? Try this:</p>\n\n<p>1 &lt;&lt; ( int) log2( x)</p>\n'}, {'answer_id': 1454990, 'author': 'dharga', 'author_id': 176554, 'author_profile': 'https://Stackoverflow.com/users/176554', 'pm_score': 2, 'selected': False, 'text': '<p>This can easily be solved with existing library calls.</p>\n\n<pre><code>int highestBit(int v){\n  return fls(v) &lt;&lt; 1;\n}\n</code></pre>\n\n<p>The Linux man page gives more details on this function and its counterparts for other input types.</p>\n'}, {'answer_id': 12376351, 'author': 'bobobobo', 'author_id': 111307, 'author_profile': 'https://Stackoverflow.com/users/111307', 'pm_score': 2, 'selected': False, 'text': "<pre><code>// Note doesn't cover the case of 0 (0 returns 1)\ninline unsigned int hibit( unsigned int x )\n{\n  unsigned int log2Val = 0 ;\n  while( x&gt;&gt;=1 ) log2Val++;  // eg x=63 (111111), log2Val=5\n  return 1 &lt;&lt; log2Val ; // finds 2^5=32\n}\n</code></pre>\n"}, {'answer_id': 14085901, 'author': 'Fabian', 'author_id': 343664, 'author_profile': 'https://Stackoverflow.com/users/343664', 'pm_score': 5, 'selected': False, 'text': '<p><code>fls</code> bottoms out to a hardware instruction on many architectures. I suspect this is probably the simplest, fastest way of doing it. </p>\n\n<pre><code>1&lt;&lt;(fls(input)-1)\n</code></pre>\n'}, {'answer_id': 30143805, 'author': 'Gavin Sellers', 'author_id': 1123590, 'author_profile': 'https://Stackoverflow.com/users/1123590', 'pm_score': 0, 'selected': False, 'text': '<p>A nifty solution I came up with is to binary search the bits.</p>\n\n<pre><code>uint64_t highestBit(uint64_t a, uint64_t bit_min, uint64_t bit_max, uint16_t bit_shift){\n    if(a == 0) return 0;\n    if(bit_min &gt;= bit_max){\n        if((a &amp; bit_min) != 0)\n            return bit_min;\n        return 0;\n    }\n    uint64_t bit_mid = bit_max &gt;&gt; bit_shift;\n    bit_shift &gt;&gt;= 1;\n    if((a &gt;= bit_mid) &amp;&amp; (a &lt; (bit_mid &lt;&lt; 1)))\n        return bit_mid;\n    else if(a &gt; bit_mid)\n        return highestBit(a, bit_mid, bit_max, bit_shift);\n    else\n        return highestBit(a, bit_min, bit_mid, bit_shift);\n\n}\n</code></pre>\n\n<p>Bit max is the highest power of 2, so for a 64 bit number it would be 2^63. Bit shift should be initialized to half the number of bits, so for 64 bits, it would be 32.</p>\n'}, {'answer_id': 30619464, 'author': 'Igor Levicki', 'author_id': 1778190, 'author_profile': 'https://Stackoverflow.com/users/1778190', 'pm_score': 2, 'selected': False, 'text': '<p>If you do not need a portable solution and your code is executing on an x86 compatible CPU you can use _BitScanReverse() intrinsic function provided by Microsoft Visual C/C++ compiler. It maps to BSR CPU instruction which returns the highest bit set.</p>\n'}, {'answer_id': 42030874, 'author': 'Kean', 'author_id': 849635, 'author_profile': 'https://Stackoverflow.com/users/849635', 'pm_score': 3, 'selected': False, 'text': "<p>Little bit late to this party but the simplest solution I found, given a modern GCC as a compiler is simply:</p>\n\n<pre><code>static inline int_t get_msb32 (register unsigned int val)\n{\n  return 32 - __builtin_clz(val);\n}\n\nstatic inline int get_msb64 (register unsigned long long val)\n{\n  return 64 - __builtin_clzll(val);\n}\n</code></pre>\n\n<p>It's even relatively portable (at the very least it will work on any GCC platform).</p>\n"}, {'answer_id': 62509101, 'author': 'Анатолий', 'author_id': 13789999, 'author_profile': 'https://Stackoverflow.com/users/13789999', 'pm_score': 2, 'selected': False, 'text': "<p>The best algorithm I like very much is:</p>\n<pre><code>unsigned hibit(unsigned n) {\n    n |= (n &gt;&gt;  1u);\n    n |= (n &gt;&gt;  2u);\n    n |= (n &gt;&gt;  4u);\n    n |= (n &gt;&gt;  8u);\n    n |= (n &gt;&gt; 16u);\n    return n - (n &gt;&gt; 1);\n}\n</code></pre>\n<p>And it's easily extended for  uint64_t like that:</p>\n<pre><code>uint64_t hibit(uint64_t n) {\n    n |= (n &gt;&gt;  1u);\n    n |= (n &gt;&gt;  2u);\n    n |= (n &gt;&gt;  4u);\n    n |= (n &gt;&gt;  8u);\n    n |= (n &gt;&gt; 16u);\n    n |= (n &gt;&gt; 32u);\n    return n - (n &gt;&gt; 1);\n}\n</code></pre>\n<p>or even to __int128</p>\n<pre><code>__int128 hibit(__int128 n) {\n    n |= (n &gt;&gt;  1u);\n    n |= (n &gt;&gt;  2u);\n    n |= (n &gt;&gt;  4u);\n    n |= (n &gt;&gt;  8u);\n    n |= (n &gt;&gt; 16u);\n    n |= (n &gt;&gt; 32u);\n    n |= (n &gt;&gt; 64u);\n    return n - (n &gt;&gt; 1);\n}\n</code></pre>\n<p>In addition is crossplatphorm solution independend of using compilator</p>\n"}]
['https://Stackoverflow.com/questions/53161', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1057/']