Re: [PATCH 9/12] generic hweight64()

[Balbir Singh <bsingharora@gmail.com>]

On 1/26/06, Akinobu Mita <mita@miraclelinux.com> wrote:
> This patch introduces the C-language equivalent of the function:
> unsigned long hweight64(__u64 w);
>
> HAVE_ARCH_HWEIGHT64_BITOPS is defined when the architecture has its own
> version of these functions.
>
> This code largely copied from:
> include/linux/bitops.h
>
> Index: 2.6-git/include/asm-generic/bitops.h
> ===================================================================
> --- 2.6-git.orig/include/asm-generic/bitops.h   2006-01-25 19:14:11.000000000 +0900
> +++ 2.6-git/include/asm-generic/bitops.h        2006-01-25 19:14:11.000000000 +0900
> @@ -491,6 +491,25 @@
>
>  #endif /* HAVE_ARCH_HWEIGHT_BITOPS */
>
> +#ifndef HAVE_ARCH_HWEIGHT64_BITOPS
> +
> +static inline unsigned long hweight64(__u64 w)
> +{
> +#if BITS_PER_LONG < 64
> +       return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w);
> +#else
> +       u64 res;
> +       res = (w & 0x5555555555555555ul) + ((w >> 1) & 0x5555555555555555ul);

This can be replaced with

res = (w-((w >> 1) & 0x5555555555555555ul));

> +       res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
> +       res = (res & 0x0F0F0F0F0F0F0F0Ful) + ((res >> 4) & 0x0F0F0F0F0F0F0F0Ful);

res = (res+(res>>4))&0x0F0F0F0F0F0F0F0Ful;

> +       res = (res & 0x00FF00FF00FF00FFul) + ((res >> 8) & 0x00FF00FF00FF00FFul);
> +       res = (res & 0x0000FFFF0000FFFFul) + ((res >> 16) & 0x0000FFFF0000FFFFul);
> +       return (res & 0x00000000FFFFFFFFul) + ((res >> 32) & 0x00000000FFFFFFFFul);
> +#endif
> +}
> +
> +#endif /* HAVE_ARCH_HWEIGHT64_BITOPS */
> +
>  #endif /* __KERNEL__ */
>
>  #endif /* _ASM_GENERIC_BITOPS_H */
> -

Please see Don Knuth's MMIXWare for more credits and improvements to this
algorithm

Balbir
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/