implement bit_length() for mp_type_int

int.to_bytes(size, byteorder) requires one to know how many bytes - size - the output is but int.bit_length() is not implemented.

>>> (1024).to_bytes(2, byteorder='big')
b'\x04\x00'
>>> (1024).to_bytes(10, byteorder='big')
b'\x00\x00\x00\x00\x00\x00\x00\x00\x04\x00'
>>> (-1024).to_bytes(10, byteorder='big', signed=True)
b'\xff\xff\xff\xff\xff\xff\xff\xff\xfc\x00'
>>> x = 1000
>>> x.to_bytes((x.bit_length() + 7) // 8, byteorder='little')
b'\xe8\x03'

Attached a patch file that implement int.bit_length()

int_length.zip

@dmazzella

@dmazzella

If you went to the trouble to implement it, why not submit a pull-request?

+1 for getting this added in.

Merge pull request micropython#4065 from weblate/weblate-circuitpytho…

Has 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.

@dlech

Attached a patch file that implement int.bit_length()

int_length.zip

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);
+    #endif

For 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 make int.bit_length work.

this patch enable MICROPY_INT_BIT_LENGTH into the file ports/unix/variants/mpconfigvariant_common.h and 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.py into the folder tests/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.patch

Ciao 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.
👍🏻

Navigation Menu

Repository navigation

implement bit_length() for mp_type_int #4065

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

implement bit_length() for mp_type_int #4065

Description

Activity

dmazzella commented on Aug 20, 2018

adritium commented on Aug 20, 2018

C4 commented on Mar 7, 2019

rkagerer commented on Feb 26, 2023

dpgeorge commented on Feb 26, 2023

massimosala commented on May 30, 2023

dmazzella commented on May 31, 2023

massimosala commented on May 31, 2023

dmazzella commented on Jun 1, 2023

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions