Programing Puzzles

[Era Scarecrow]

Koroskin Denis wrote:
> 
> > JAnderson wrote:
> >> Wyverex wrote:
> >>> just some fun little programming puzzles I
> found around online...
> >>>
> >>>
> >>> Problem #2 Test if an int is even or odd
> without looping or if  
> >>> statement (Cant use: do, while, for, foreach,
> if).
> >>>
> >>> Problem #4 Find if the given number is a power
> of 2.
> >>>
> >>> Post Solutions to this root, comments to
> someones solution in that  
> >>> thread.
> >>   Some of these are pretty standard interview
> questions. Although I  
> >> don't personally like to ask these sort of
> questions because they are  
> >> often about knowing a "trick" which you
> an easily lookup.  The can be  
> >> 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
> less then 15 operations  
> >> 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
> & 4 ? 1 : 0) + (i & 8 ? 1 :  
> > 0);
> >     i >>= 4;
> >     c += (i & 1) + (i & 2 ? 1 : 0) + (i &
> 4 ? 1 : 0) + (i & 8 ? 1 : 0);
> >     i >>= 4;
> >     c += (i & 1) + (i & 2 ? 1 : 0) + (i &
> 4 ? 1 : 0) + (i & 8 ? 1 : 0);
> >     i >>= 4;
> >     c += (i & 1) + (i & 2 ? 1 : 0) + (i &
> 4 ? 1 : 0) + (i & 8 ? 1 : 0);
> >
> >     return c;
> > }
> >
> > int count2( in int i )
> > {
> >     int c = (i & 1) + ((i >> 1) & 1) +
> ((i >> 2) & 1) + ((i >> 3) & 1);
> >     i >>= 4;
> >     c += (i & 1) + ((i >> 1) & 1) + ((i
> >> 2) & 1) + ((i >> 3) & 1);
> >     i >>= 4;
> >     c += (i & 1) + ((i >> 1) & 1) + ((i
> >> 2) & 1) + ((i >> 3) & 1);
> >     i >>= 4;
> >     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);
}