Đếm số chữ số của số nhị phân


(Monitor of A2_K22_CVP) #1

Mọi người cho em hỏi có cách nào để biết được số bit có nghĩa của một số nguyên kiểu int không ạ?
Hay là ngoài cách sử dụng vòng lặp ra thì có cách nào đếm được số chữ số của một số nguyên kiểu int sau khi chuyển sang hệ nhị phân ko ạ?
Em cảm ơn rất nhiều!!


(SITUVN.gcd) #2

Chưa hiểu câu hỏi của bạn. Bạn cho ví dụ được không?


(Vuio) #3

Bạn cần tìm lũy thừa của 2 bé nhất mà lớn hơn số N.

2^X > N

thì X chính là số bit cần thiết.
Ví dụ đi, cho số

N = 0    -> X = 0 vì 2^0 > 0
N = 1    -> X = 1 vì 2^1 > 1
N = 2    -> X = 2 vì 2^2 > 2 (2^1 không được vì phải lớn hơn, không được bằng)
N = 100  -> X = 7 vì 2^7 = 128 > 100

(Monitor of A2_K22_CVP) #5

Vuio
Theo em thì cách đó vẫn cần dùng đến vòng lặp đúng ko ạ?


(Monitor of A2_K22_CVP) #6

Tức là giả sử em có số 32 chẳng hạn, em muốn đếm số chữ số 0 và số chữ số 1 của nó sau khi được chuyển sang hệ nhị phân.
Số 32 sau khi chuyển sang hệ nhị phân là 10000 nhưng khi vào máy tính dưới dạng kiểu int thì nó sẽ là 32 bit như thế này đúng ko ạ: 000…00010000
Ý em hỏi là có cách nào đếm được số chữ số của nó trong hệ nhị phân ko ấy ạ, nhưng dựa trên việc đếm số bit có nghĩa!
Hình như em nói vẫn hơi khó hiểu :frowning:


(SITUVN.gcd) #7
int x = round(log2(n))

Đây là mã nguồn của phương thức tính các bit 0 đầu tiên trong java.

    public static int numberOfLeadingZeros(int i) {
        if (i == 0)
            return 32;
        int n = 1;
        if (i >>> 16 == 0) { n += 16; i <<= 16; }
        if (i >>> 24 == 0) { n +=  8; i <<=  8; }
        if (i >>> 28 == 0) { n +=  4; i <<=  4; }
        if (i >>> 30 == 0) { n +=  2; i <<=  2; }
        n -= i >>> 31;
        return n;
    }
int x = 32 - numberOfLeadingZeros(n)

(rogp10) #8

“clz intrinsic”, O(1) (aka count leading zeroes)
Nếu không muốn thì tham khảo bit trick (như post trên). Bản chất của nó là chặt nhị phân.


(Vuio) #9

Dùng log cơ số 2 với hàm làm tròn lên (ceil)

X = ceil(log2(N + 1));

Thiếu một số 0. Số 32 phải là 100000


(Monitor of A2_K22_CVP) #10

Em rất cảm ơn mọi người đã giúp đỡ ạ!


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?