Feature #8748 ยป popcount.patch
| configure.in (working copy) | ||
|---|---|---|
|
RUBY_CHECK_BUILTIN_FUNC(__builtin_clz, [__builtin_clz(0)])
|
||
|
RUBY_CHECK_BUILTIN_FUNC(__builtin_clzl, [__builtin_clzl(0)])
|
||
|
RUBY_CHECK_BUILTIN_FUNC(__builtin_clzll, [__builtin_clzll(0)])
|
||
|
RUBY_CHECK_BUILTIN_FUNC(__builtin_popcount, [__builtin_popcount(0)])
|
||
|
RUBY_CHECK_BUILTIN_FUNC(__builtin_popcountl, [__builtin_popcountl(0)])
|
||
|
RUBY_CHECK_BUILTIN_FUNC(__builtin_popcountll, [__builtin_popcountll(0)])
|
||
|
# Some platform need -lrt for clock_gettime, but the other don't.
|
||
|
if test x"$ac_cv_func_clock_gettime" != xyes; then
|
||
| numeric.c (working copy) | ||
|---|---|---|
|
/*
|
||
|
* call-seq:
|
||
|
* int.popcount -> integer
|
||
|
*
|
||
|
* Returns the number of one bits in the absolute number of +int+.
|
||
|
*
|
||
|
* 0.popcount #=> 0
|
||
|
* 0b1010.popcount #=> 2
|
||
|
* (-0b1011).popcount #=> 3
|
||
|
*/
|
||
|
static VALUE
|
||
|
fix_popcount(VALUE num)
|
||
|
{
|
||
|
long i = FIX2LONG(num);
|
||
|
if (i < 0)
|
||
|
i = -i;
|
||
|
return LONG2FIX(popcount_long((unsigned long)i));
|
||
|
}
|
||
|
/*
|
||
|
* call-seq:
|
||
|
* int.next -> integer
|
||
|
* int.succ -> integer
|
||
|
*
|
||
| ... | ... | |
|
rb_define_method(rb_cFixnum, "odd?", fix_odd_p, 0);
|
||
|
rb_define_method(rb_cFixnum, "even?", fix_even_p, 0);
|
||
|
rb_define_method(rb_cFixnum, "succ", fix_succ, 0);
|
||
|
rb_define_method(rb_cFixnum, "popcount", fix_popcount, 0);
|
||
|
rb_cFloat = rb_define_class("Float", rb_cNumeric);
|
||
| bignum.c (working copy) | ||
|---|---|---|
|
}
|
||
|
/*
|
||
|
* call-seq:
|
||
|
* int.popcount -> integer
|
||
|
*
|
||
|
* Returns the number of one bits in the absolute number of +int+.
|
||
|
*
|
||
|
* (2**100).popcount #=> 1
|
||
|
* (2**100-1).popcount #=> 100
|
||
|
* (-2**100).popcount #=> 1
|
||
|
* (10**100).popcount #=> 105
|
||
|
* (257**257).popcount #=> 999
|
||
|
*/
|
||
|
static VALUE
|
||
|
rb_big_popcount(VALUE num)
|
||
|
{
|
||
|
long n = RBIGNUM_LEN(num);
|
||
|
BDIGIT *ds = BDIGITS(num);
|
||
|
VALUE result = LONG2FIX(0);
|
||
|
long r = 0;
|
||
|
int pop;
|
||
|
while (0 < n) {
|
||
|
n--;
|
||
|
#if SIZEOF_BDIGITS <= SIZEOF_INT
|
||
|
pop = popcount_int((unsigned int)ds[n]);
|
||
|
#elif SIZEOF_BDIGITS <= SIZEOF_LONG
|
||
|
pop = popcount_long((unsigned long)ds[n]);
|
||
|
#elif defined(HAVE_LONG_LONG) && SIZEOF_BDIGITS <= SIZEOF_LONG_LONG
|
||
|
pop = popcount_long_long((unsigned LONG_LONG)ds[n]);
|
||
|
#else
|
||
|
# error too big BDIGIT type.
|
||
|
#endif
|
||
|
r += pop;
|
||
|
if (FIXNUM_MAX < r) {
|
||
|
if (result == LONG2FIX(0))
|
||
|
result = rb_uint2big(r);
|
||
|
else
|
||
|
result = bigadd_int(result, r);
|
||
|
}
|
||
|
}
|
||
|
if (r != 0) {
|
||
|
if (result == LONG2FIX(0))
|
||
|
result = LONG2NUM(r);
|
||
|
else
|
||
|
result = bigadd_int(result, r);
|
||
|
}
|
||
|
return result;
|
||
|
}
|
||
|
/*
|
||
|
* Bignum objects hold integers outside the range of
|
||
|
* Fixnum. Bignum objects are created
|
||
|
* automatically when integer calculations would otherwise overflow a
|
||
| ... | ... | |
|
rb_define_method(rb_cBignum, "size", rb_big_size, 0);
|
||
|
rb_define_method(rb_cBignum, "odd?", rb_big_odd_p, 0);
|
||
|
rb_define_method(rb_cBignum, "even?", rb_big_even_p, 0);
|
||
|
rb_define_method(rb_cBignum, "popcount", rb_big_popcount, 0);
|
||
|
power_cache_init();
|
||
|
}
|
||
| internal.h (working copy) | ||
|---|---|---|
|
# endif
|
||
|
#endif
|
||
|
#define MASK_8x2(mask) (((mask) << 8) | (mask))
|
||
|
#define MASK_8x4(mask) ((MASK_8x2(mask) << 16) | MASK_8x2(mask))
|
||
|
#define MASK_8x8(mask) ((MASK_8x4(mask) << 32) | MASK_8x4(mask))
|
||
|
#define MASK_8x16(mask) ((MASK_8x8(mask) << 64) | MASK_8x8(mask))
|
||
|
#if SIZEOF_INT * CHAR_BIT <= 16
|
||
|
# define MASK_INT(byte) MASK_8x2((unsigned int)(byte))
|
||
|
#elif SIZEOF_INT * CHAR_BIT <= 32
|
||
|
# define MASK_INT(byte) MASK_8x4((unsigned int)(byte))
|
||
|
#elif SIZEOF_INT * CHAR_BIT <= 64
|
||
|
# define MASK_INT(byte) MASK_8x8((unsigned int)(byte))
|
||
|
#elif SIZEOF_INT * CHAR_BIT <= 128
|
||
|
# define MASK_INT(byte) MASK_8x16((unsigned int)(byte))
|
||
|
#else
|
||
|
# error too big integer type
|
||
|
#endif
|
||
|
#if SIZEOF_LONG * CHAR_BIT <= 16
|
||
|
# define MASK_LONG(byte) MASK_8x2((unsigned long)(byte))
|
||
|
#elif SIZEOF_LONG * CHAR_BIT <= 32
|
||
|
# define MASK_LONG(byte) MASK_8x4((unsigned long)(byte))
|
||
|
#elif SIZEOF_LONG * CHAR_BIT <= 64
|
||
|
# define MASK_LONG(byte) MASK_8x8((unsigned long)(byte))
|
||
|
#elif SIZEOF_LONG * CHAR_BIT <= 128
|
||
|
# define MASK_LONG(byte) MASK_8x16((unsigned long)(byte))
|
||
|
#else
|
||
|
# error too big integer type
|
||
|
#endif
|
||
|
#ifdef HAVE_LONG_LONG
|
||
|
# if SIZEOF_LONG_LONG * CHAR_BIT <= 16
|
||
|
# define MASK_LONG_LONG(byte) MASK_8x2((unsigned LONG_LONG)(byte))
|
||
|
# elif SIZEOF_LONG_LONG * CHAR_BIT <= 32
|
||
|
# define MASK_LONG_LONG(byte) MASK_8x4((unsigned LONG_LONG)(byte))
|
||
|
# elif SIZEOF_LONG_LONG * CHAR_BIT <= 64
|
||
|
# define MASK_LONG_LONG(byte) MASK_8x8((unsigned LONG_LONG)(byte))
|
||
|
# elif SIZEOF_LONG_LONG * CHAR_BIT <= 128
|
||
|
# define MASK_LONG_LONG(byte) MASK_8x16((unsigned LONG_LONG)(byte))
|
||
|
# else
|
||
|
# error too big integer type
|
||
|
# endif
|
||
|
#endif
|
||
|
#if defined(HAVE_BUILTIN___BUILTIN_POPCOUNT)
|
||
|
# define popcount_int(x) __builtin_popcount(x)
|
||
|
#else
|
||
|
static inline int
|
||
|
popcount_int(unsigned int x)
|
||
|
{
|
||
|
x -= (x >> 1) & MASK_INT(0x55);
|
||
|
x = ((x >> 2) & MASK_INT(0x33)) + (x & MASK_INT(0x33));
|
||
|
x = ((x >> 4) + x) & MASK_INT(0x0f);
|
||
|
x += (x >> 8);
|
||
|
x += (x >> 16);
|
||
|
#if 32 < SIZEOF_INT * CHAR_BIT
|
||
|
x += (x >> 32);
|
||
|
#endif
|
||
|
#if 64 < SIZEOF_INT * CHAR_BIT
|
||
|
x += (x >> 64);
|
||
|
#endif
|
||
|
#if 128 < SIZEOF_INT * CHAR_BIT
|
||
|
# error too big integer type
|
||
|
#endif
|
||
|
return (int)(x & 0xff);
|
||
|
}
|
||
|
#endif
|
||
|
#if defined(HAVE_BUILTIN___BUILTIN_POPCOUNTL)
|
||
|
# define popcount_long(x) __builtin_popcountl(x)
|
||
|
#else
|
||
|
static inline int
|
||
|
popcount_long(unsigned long x)
|
||
|
{
|
||
|
x -= (x >> 1) & MASK_LONG(0x55);
|
||
|
x = ((x >> 2) & MASK_LONG(0x33)) + (x & MASK_LONG(0x33));
|
||
|
x = ((x >> 4) + x) & MASK_LONG(0x0f);
|
||
|
x += (x >> 8);
|
||
|
x += (x >> 16);
|
||
|
#if 32 < SIZEOF_LONG * CHAR_BIT
|
||
|
x += (x >> 32);
|
||
|
#endif
|
||
|
#if 64 < SIZEOF_LONG * CHAR_BIT
|
||
|
x += (x >> 64);
|
||
|
#endif
|
||
|
#if 128 < SIZEOF_LONG * CHAR_BIT
|
||
|
# error too big integer type
|
||
|
#endif
|
||
|
return (int)(x & 0xff);
|
||
|
}
|
||
|
#endif
|
||
|
#ifdef HAVE_LONG_LONG
|
||
|
# if defined(HAVE_BUILTIN___BUILTIN_POPCOUNTLL)
|
||
|
# define popcount_long_long(x) __builtin_popcountll(x)
|
||
|
# else
|
||
|
static inline int
|
||
|
popcount_long_long(unsigned LONG_LONG x)
|
||
|
{
|
||
|
x -= (x >> 1) & MASK_LONG_LONG(0x55);
|
||
|
x = ((x >> 2) & MASK_LONG_LONG(0x33)) + (x & MASK_LONG_LONG(0x33));
|
||
|
x = ((x >> 4) + x) & MASK_LONG_LONG(0x0f);
|
||
|
x += (x >> 8);
|
||
|
x += (x >> 16);
|
||
|
#if 32 < SIZEOF_LONG_LONG * CHAR_BIT
|
||
|
x += (x >> 32);
|
||
|
#endif
|
||
|
#if 64 < SIZEOF_LONG_LONG * CHAR_BIT
|
||
|
x += (x >> 64);
|
||
|
#endif
|
||
|
#if 128 < SIZEOF_LONG_LONG * CHAR_BIT
|
||
|
# error too big integer type
|
||
|
#endif
|
||
|
return (int)(x & 0xff);
|
||
|
}
|
||
|
# endif
|
||
|
#endif
|
||
|
struct rb_deprecated_classext_struct {
|
||
|
char conflict[sizeof(VALUE) * 3];
|
||
|
};
|
||
| test/ruby/test_integer.rb (working copy) | ||
|---|---|---|
|
end
|
||
|
assert_equal(3 ^ 10, 3 ^ obj)
|
||
|
end
|
||
|
def test_popcount
|
||
|
assert_equal(1, -1.popcount)
|
||
|
assert_equal(0, 0.popcount)
|
||
|
assert_equal(1, 1.popcount)
|
||
|
-100.upto(100) {|n|
|
||
|
assert_equal(n.abs.to_s(2).count("1"), n.popcount)
|
||
|
}
|
||
|
0.upto(100) {|k|
|
||
|
n = 3**k
|
||
|
assert_equal(n.abs.to_s(2).count("1"), n.popcount)
|
||
|
n = -n
|
||
|
assert_equal(n.abs.to_s(2).count("1"), n.popcount)
|
||
|
}
|
||
|
end
|
||
|
end
|
||