10000 py/objint.c: Add support for int.bit_length · micropython/micropython@056b4dd · GitHub
[go: up one dir, main page]
Skip to content

Commit 056b4dd

Browse files
dmazzellajimmo
dmazzella
authored and
jimmo
committed
py/objint.c: Add support for int.bit_length
1 parent a79a6ab commit 056b4dd

File tree

9 files changed

+102
-0
lines changed

9 files changed

+102
-0
lines changed

‎py/mpconfig.h

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1144,6 +1144,11 @@ typedef double mp_float_t;
11441144
#define MICROPY_PY_BUILTINS_ROUND_INT (MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_EXTRA_FEATURES)
11451145
#endif
11461146

1147+
// Whether to support int.bit_length(n)
1148+
#ifndef MICROPY_PY_BUILTINS_INT_BIT_LENGTH
1149+
#define MICROPY_PY_BUILTINS_INT_BIT_LENGTH (MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_EXTRA_FEATURES)
1150+
#endif
1151+
11471152
// Whether to support complete set of special methods for user
11481153
// classes, or only the most used ones. "Inplace" methods are
11491154
// controlled by MICROPY_PY_ALL_INPLACE_SPECIAL_METHODS below.

‎py/mpz.c

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1390,6 +1390,21 @@ void mpz_pow3_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs, const mpz_t
13901390
mpz_free(n);
13911391
}
13921392

1393+
#if MICROPY_PY_BUILTINS_INT_BIT_LENGTH
1394+
mp_uint_t mpz_bit_length_inpl(mpz_t *n) {
1395+
if (n->len == 0) {
1396+
return 0;
1397+
}
1398+
mpz_dig_t d = n->dig[n->len - 1];
1399+
mp_uint_t num_bits = 0;
1400+
while (d) {
1401+
d >>= 1;
1402+
++num_bits;
1403+
}
1404+
return MPZ_DIG_SIZE * (n->len - 1) + num_bits;
1405+
}
1406+
#endif
1407+
13931408
#if 0
13941409
these functions are unused
13951410

‎py/mpz.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -138,6 +138,9 @@ void mpz_and_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
138138
void mpz_or_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
139139
void mpz_xor_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
140140
void mpz_divmod_inpl(mpz_t *dest_quo, mpz_t *dest_rem, const mpz_t *lhs, const mpz_t *rhs);
141+
#if MICROPY_PY_BUILTINS_INT_BIT_LENGTH
142+
mp_uint_t mpz_bit_length_inpl(mpz_t *dest);
143+
#endif
141144

142145
static inline size_t mpz_max_num_bits(const mpz_t *z) {
143146
return z->len * MPZ_DIG_SIZE;

‎py/objint.c

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -367,6 +367,22 @@ mp_int_t mp_obj_int_get_checked(mp_const_obj_t self_in) {
367367
return MP_OBJ_SMALL_INT_VALUE(self_in);
368368
}
369369

370+
#if MICROPY_PY_BUILTINS_INT_BIT_LENGTH
371+
STATIC mp_obj_t int_bit_length(mp_obj_t self_in) {
372+
mp_int_t val = MP_OBJ_SMALL_INT_VALUE(self_in);
373+
if (val < 0) {
374+
val = -val;
375+
}
376+
mp_uint_t n = 0;
377+
while (val) {
378+
val >>= 1;
379+
++n;
380+
}
381+
return MP_OBJ_NEW_SMALL_INT(n);
382+
}
383+
MP_DEFINE_CONST_FUN_OBJ_1(int_bit_length_obj, int_bit_length);
384+
#endif
385+
370386
#endif // MICROPY_LONGINT_IMPL == MICROPY_LONGINT_IMPL_NONE
371387

372388
// This dispatcher function is expected to be independent of the implementation of long int
@@ -453,6 +469,9 @@ STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(int_to_bytes_obj, 3, 4, int_to_bytes)
453469
STATIC const mp_rom_map_elem_t int_locals_dict_table[] = {
454470
{ MP_ROM_QSTR(MP_QSTR_from_bytes), MP_ROM_PTR(&int_from_bytes_obj) },
455471
{ MP_ROM_QSTR(MP_QSTR_to_bytes), MP_ROM_PTR(&int_to_bytes_obj) },
472+
#if MICROPY_PY_BUILTINS_INT_BIT_LENGTH
473+
{ MP_ROM_QSTR(MP_QSTR_bit_length), MP_ROM_PTR(&int_bit_length_obj) },
474+
#endif
456475
};
457476

458477
STATIC MP_DEFINE_CONST_DICT(int_locals_dict, int_locals_dict_table);

‎py/objint.h

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -62,4 +62,6 @@ mp_obj_t mp_obj_int_binary_op(mp_binary_op_t op, mp_obj_t lhs_in, mp_obj_t rhs_i
6262
mp_obj_t mp_obj_int_binary_op_extra_cases(mp_binary_op_t op, mp_obj_t lhs_in, mp_obj_t rhs_in);
6363
mp_obj_t mp_obj_int_pow3(mp_obj_t base, mp_obj_t exponent, mp_obj_t modulus);
6464

65+
MP_DECLARE_CONST_FUN_OBJ_1(int_bit_length_obj);
66+
6567
#endif // MICROPY_INCLUDED_PY_OBJINT_H

‎py/objint_longlong.c

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -292,4 +292,21 @@ mp_float_t mp_obj_int_as_float_impl(mp_obj_t self_in) {
292292
}
293293
#endif
294294

295+
#if MICROPY_PY_BUILTINS_INT_BIT_LENGTH
296+
STATIC mp_obj_t int_bit_length(mp_obj_t self_in) {
297+
mp_obj_int_t *self = self_in;
298+
long long val = self->val;
299+
if (val < 0) {
300+
val = -val;
301+
}
302+
mp_uint_t n = 0;
303+
while (val) {
304+
val >>= 1;
305+
++n;
306+
}
307+
return MP_OBJ_NEW_SMALL_INT(n);
308+
}
309+
MP_DEFINE_CONST_FUN_OBJ_1(int_bit_length_obj, int_bit_length);
310+
#endif
311+
295312
#endif

‎py/objint_mpz.c

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -457,4 +457,25 @@ mp_float_t mp_obj_int_as_float_impl(mp_obj_t self_in) {
457457
}
458458
#endif
459459

460+
#if MICROPY_PY_BUILTINS_INT_BIT_LENGTH
461+
STATIC mp_obj_t int_bit_length(mp_obj_t self_in) {
462+
if (mp_obj_is_small_int(self_in)) {
463+
mp_int_t val = MP_OBJ_SMALL_INT_VALUE(self_in);
464+
if (val < 0) {
465+
val = -val;
466+
}
467+
mp_uint_t n = 0;
468+
while (val) {
469+
val >>= 1;
470+
++n;
471+
}
472+
return MP_OBJ_NEW_SMALL_INT(n);
473+
} else {
474+
mp_obj_int_t *self = MP_OBJ_TO_PTR(self_in);
475+
return MP_OBJ_NEW_SMALL_INT(mpz_bit_length_inpl(&self->mpz));
476+
}
477+
}
478+
MP_DEFINE_CONST_FUN_OBJ_1(int_bit_length_obj, int_bit_length);
479+
#endif
480+
460481
#endif

‎tests/basics/builtin_help.py.exp

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,9 +3,11 @@ object <function> is of type function
33
object <class 'int'> is of type type
44
from_bytes -- <classmethod>
55
to_bytes -- <function>
6+
########
67
object 1 is of type int
78
from_bytes -- <classmethod>
89
to_bytes -- <function>
10+
########
911
object <module 'micropython'> is of type module
1012
__name__ -- micropython
1113
const -- <function>

‎tests/basics/int_bit_length.py

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
# tests int.bit_length
2+
3+
try:
4+
int.bit_length
5+
except AttributeError:
6+
print('SKIP')
7+
raise SystemExit
8+
9+
for n in (0, 37, 1024, 1<<29, 1<<30, 1<<31, 1<<32, 1<<61, 1<<62, 1<<63, 1<<64):
10+
for j in (-1921, -302, -3, -2, -1, 0, 1, 2, 3, 1821):
11+
for s in (-1, 1):
12+
x = (s * (n+j))
13+
print(x, x.bit_length())
14+
15+
print((2048).bit_length())
16+
print((-2048).bit_length())
17+
18+
print(int.bit_length(5))

0 commit comments

Comments
 (0)
0