tag:blogger.com,1999:blog-2543858175797658864.post1453578986847491542..comments2023-06-03T09:48:30.964-04:00Comments on Trash Can of Code: Checking if an Integer is a Power of 2cottonvibeshttp://www.blogger.com/profile/15542648017139504620noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-2543858175797658864.post-39051829300685463202012-06-04T19:46:04.939-04:002012-06-04T19:46:04.939-04:00Note that the second method depends on the interna...Note that the second method depends on the internal representation of negative integers. In some rare cases (when negative integers are not represented as 2's complement) this method won't work.Martin Kunevhttps://www.blogger.com/profile/17823125560498321991noreply@blogger.comtag:blogger.com,1999:blog-2543858175797658864.post-89028114497163080502010-09-18T20:17:50.686-04:002010-09-18T20:17:50.686-04:00Yeh popcnt is probably like ~2 times faster since ...Yeh popcnt is probably like ~2 times faster since you can just do something like:<br /><br />bool isPow2(uint n) {<br /> return _mm_popcnt_u32(n) == 1;<br />}<br /><br />The main benefit is that you're only doing 1 comparison whereas the versions I showed have to do 2 comparisons (they need to check if the value is non-zero to return the correct result when n==0).<br /><br />Of-course the main drawback is that popcnt is only available on modern machines, and not a lot of people have SSE4.2 or SSE4a currently.<br />And yes there's some cpuid bit to check for support of this instruction individually, but i wonder what processor would support this instruction and not support SSE4.2 or SSE4a (i guess maybe some cpu aimed for netbooks).cottonvibeshttps://www.blogger.com/profile/15542648017139504620noreply@blogger.comtag:blogger.com,1999:blog-2543858175797658864.post-22771647822670688952010-09-18T12:02:23.706-04:002010-09-18T12:02:23.706-04:00SSE4.2 (nehalem+ (aka core i3/5/7)) and SSE4a (amd...SSE4.2 (nehalem+ (aka core i3/5/7)) and SSE4a (amd 10h) processors support 'popcnt' operation, i.e. population count. Its result is the number of set bits in bit string. This operation might also be supported by other processors, as there is cpuid bit just for that.<br />Haven't checked it myself with documentation, but if you need more than one variable to be exactly a power of 2, this might prove faster. For one shot it would probably be as fast as the final versions you presented, due to branch 'if (hasPopCnt) {...} else {...}'.janisozaurhttps://www.blogger.com/profile/07044283505755380535noreply@blogger.com