Repository navigation
implement bit_length() for mp_type_int #4065
Description
Activity
Attached a patch file that implement int.bit_length()
Reacted by anddam and Artem SmotrakovIf you went to the trouble to implement it, why not submit a pull-request?
+1 for getting this added in.
Reacted by Andre Lucio, rdagger and rkagererHas this still not been merged?
Has this still not been merged?
There is no pull request for this feature, so nothing to review and merge.
Attached a patch file that implement int.bit_length()
Hi Damiano
I request for bit_length on #11618 and I discover your work, thank to @dlech
It is the first time I see mpn/mpz, but reading its header it seems to me this optimization is possible:
+ if(n->len == 0) { + return 0; + } + mpz_t *dest = mpz_clone(n); + mp_uint_t num_bits = 0; while (dest->len > 1) { dest->len = mpn_shr(dest->dig, dest->dig, dest->len, MPZ_DIG_SIZE); num_bits += MPZ_DIG_SIZE; } + while (dest->len > 0) { + dest->len = mpn_shr(dest->dig, dest->dig, dest->len, 1); + num_bits++; + }
How can we make this a PR ?
Hmh, if there's any doubts about its impact on flash space... what about an implementation that only works on CPU native integers?
I mean in your code taking away the mpn/mpz stuff, something like...
+#if MICROPY_INT_BIT_LENGTH +STATIC mp_obj_t int_bit_length(size_t n_args, const mp_obj_t *args) { + (void)n_args; + #if MICROPY_LONGINT_IMPL == MICROPY_LONGINT_IMPL_MPZ + ... raise NotImplementedError ... + #else + mp_uint_t dest = MP_OBJ_SMALL_INT_VALUE(args[0]); + mp_uint_t num_bits = 0; + while (dest > 0) { + dest >>= 1; + num_bits++; + } + return mp_obj_new_int_from_uint(num_bits); + #endifFor cases (computing custom hashes, bit-banging, ...) where I see _ bit_length _ useful, you use at most 32 bit usigned int.
If it's not blasphemy to have a specialized version, I also ask for the implementation of bit_count
It is not present in Python, but here we are in Micropython and we work close to metal. Again for the same use cases mentioned above.
These specialized version (not mpn/mpz) of bit_length and bit_count will take a few bytes.
Ciao Massimo,
I am attaching an updated version of the patch file to makeint.bit_lengthwork.this patch enable
MICROPY_INT_BIT_LENGTHinto the fileports/unix/variants/mpconfigvariant_common.hand unix port can be used for test.Try it and let me know if it works correctly.
this is a test for him, create the file
int_bit_length.pyinto the foldertests/basics/and paste:# tests int.bit_length n = -37 print(n.bit_length()) n = 1024 print(n.bit_length()) n = -1024 print(n.bit_length()) print((2048).bit_length()) print((-2048).bit_length())If everything works correctly I will proceed to create a PR for this
Greetings,
D.
int_bit_length.patchCiao Damiano
What about the possible optimization in the mpn/mpz code path?
For the testing: sorry, I just started developing on MP and I still haven't tried to install the toolchain and compile a firmware.
What about the possible optimization in the mpn/mpz code path?
For this we can wait tests/PR
For the testing: sorry, I just started developing on MP and I still haven't tried to install the toolchain and compile a firmware.
👍🏻
int.to_bytes(size, byteorder) requires one to know how many bytes -
size- the output is butint.bit_length()is not implemented.