• Era Scarecrow <rtcvb32 yahoo.com> Aug 15 2008

Era Scarecrow <rtcvb32 yahoo.com> writes:

Koroskin Denis wrote:
 
 JAnderson wrote:
 Wyverex wrote:
 just some fun little programming puzzles I






 Problem #2 Test if an int is even or odd






 statement (Cant use: do, while, for, foreach,






 Problem #4 Find if the given number is a power






 Post Solutions to this root, comments to






 thread.






 don't personally like to ask these sort of




 often about knowing a "trick" which you




 fun to figure out though.
  Here's another common one:
  | Write a bitcount for a 32-bit number.
  And a little more challenging:
  | Write a bitcount for a 32-bit number that is




 without using a lookup table.
  | Can you do that in 12 or less?
  -Joel


 int count( in int i )
 {
     int c = (i & 1) + (i & 2 ? 1 : 0) + (i


 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i &


     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i &


     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i &


     return c;
 }

 int count2( in int i )
 {
     int c = (i & 1) + ((i >> 1) & 1) +


     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i
 2) & 1) + ((i >> 3) & 1);


     c += (i & 1) + ((i >> 1) & 1) + ((i
 2) & 1) + ((i >> 3) & 1);


     c += (i & 1) + ((i >> 1) & 1) + ((i
 2) & 1) + ((i >> 3) & 1);


     return c;
 }


 Much simpler:
 
 int getBitCount32(int i) {
      return getBitCount16(i) + getBitCount16(i >>
 16);
 }
 
 int getBitCount16(int i) {
      return getBitCount8(i) + getBitCount8(i >> 8);
 }
 
 int getBitCount8(int i) {
      return getBitCount4(i) + getBitCount4(i >> 4);
 }
 
 int getBitCount4(int i) {
      return getBitCount2(i) + getBitCount2(i >> 2);
 }
 
 int getBitCount2(int i) {
      return (i & 2) + (i & 1);
 }


 Although untested, would this qualify? I don't see any logic problems.

 int getBitCount(int i){
    int b = i & 1;
    i = i >>> 1;    //force unsigned shift
    return b + (i ? getBitCount(i) : 0);
}