Chuyển đổi số thập phân thành nhị phân trong Haskell

Question

Tôi đã tìm ra đoạn mã này hoạt động, nhưng tôi không hiểu tại sao nó lại hoạt động. Nó chuyển đổi một Int thành biểu diễn của nó theo dạng nhị phân.

repBinario::Int -> Int 
repBinario 0 = 0 
repBinario x = 10 * repBinario (x `div` 2) + x `mod` 2 

Tôi biết những gì div và mod làm. Tuy nhiên, làm cách nào để đặt mỗi số xuất phát từ mod cùng nhau?

Answer 1

Tóm lại, nó nhân kết quả tích lũy theo số 10 trên mỗi lần lặp lại.

Để hiểu rõ hơn về những gì đang xảy ra, chúng tôi có thể chia chức năng của bạn thành hai đơn giản hơn. Việc đầu tiên sẽ chuyển đổi một số nguyên thành một danh sách các chữ số nhị phân. Người kia sau đó sẽ làm chính xác điều làm phiền bạn: concat một danh sách các chữ số nhị phân thành một số nguyên.

extractBinDigits :: Int -> [Int] 
extractBinDigits = 
    unfoldr (\x -> if x == 0 then Nothing else Just (mod x 2, div x 2)) 

concatDigits :: [Int] -> Int 
concatDigits = 
    foldr (\a b -> a + b * 10) 0 

Như bạn thấy, chúng tôi chỉ cần gấp danh sách nhân bộ tích lũy theo 10 trên mỗi bước và thêm từng chữ số vào nó.

Sau đó, chức năng ban đầu của bạn sẽ trở thành chỉ này:

repBinario :: Int -> Int 
repBinario = 
    concatDigits . extractBinDigits 

Division bây giờ cho phép chúng tôi kiểm tra và tái sử dụng các mảnh tốt hơn của chương trình của chúng tôi cung cấp cho chúng ta linh hoạt hơn. Ví dụ, bằng cách thêm một chức năng đơn giản bây giờ bạn có thể chuyển đổi các số nguyên vào một chuỗi trong một đi:

showDigits :: [Int] -> String 
showDigits = 
    reverse . map (chr . (+ 48)) 

repStringyBinario :: Int -> String 
repStringyBinario = 
    showDigits . extractBinDigits 

Answer 2

Hãy cùng xem qua một ví dụ, sau đó:

repBinario 5 

định nghĩa thay thế của repBinario 5:

10 * repBinario (5 `div` 2) + 5 `mod` 2 

Giảm div và mod:

10 * repBinario 2 + 1 
        ^

Ở đây chúng tôi đã tạo ra chữ số đầu tiên của chúng tôi, được đánh dấu bằng ^.

định nghĩa thay thế của repBinario 2:

10 * (10 * repBinario (2 `div` 2) + 2 `mod` 2) + 1 
               ^

Giảm div và mod:

10 * (10 * repBinario 1 + 0) + 1 
         ^^

định nghĩa thay thế của repBinario 1:

10 * (10 * (10 * repBinario (1 `div` 2) + 1 `mod` 2) + 0) + 1 
                ^^

Giảm div và mod:

10 * (10 * (10 * repBinario 0 + 1) + 0) + 1 
           ^^^

định nghĩa thay thế của repBinario 0:

10 * (10 * (10 * 0 + 1) + 0) + 1 
        ^^^

Giảm:

101 

Tại mỗi bước, (`mod` 2) được các chữ số nhị phân có ý nghĩa nhất, và (`div` 2) chuyển số rightward , loại bỏ chữ số và chuyển số còn lại của số đó một cách đệ quy o divBinario. Cuối cùng, chúng tôi thực hiện quy trình ngược lại: (+ d) thêm chữ số hiện tại vào kết quả và (* 10) thay đổi số sang trái để chúng tôi có thể thêm nhiều chữ số hơn.

Những gì bạn nhận được là một số thập phân mà trông giống hệt với biểu diễn nhị phân của đầu vào gốc.

Nếu bạn loại bỏ các nhân bởi 10, bạn sẽ có được popCount, một chức năng cung cấp cho bạn các tính dân một số-số lượng 1 bit trong biểu diễn nhị phân của nó:

popCount 0 = 0 
popCount x = popCount (x `div` 2) + x `mod` 2 

popCount 5 == 2 

Answer 3

Tôi nghĩ rằng nó sẽ tốt nhất để tính toán hàm này cho một giá trị nhỏ bằng tay - điều này là có thể vì đây là hàm thuần túy do đó bạn có thể thay thế mặt bên trái bằng định nghĩa của nó (nghĩa là mặt bên phải) - từ khoa học máy tính ưa thích cho tính năng này là " tính minh bạch tham chiếu ".

repBinario 24 = 10 * repBinario (24 `div` 2) + 24 `mod` 2 
       = 10 * repBinario 12 + 0 
       = 10 * (10 * repBinario (12 `div` 2) + 12 `mod` 2) 
       = 100 * repBinario 6 + 0 
       = 100 * (10 * repBinario (6 `div` 2) + 6 `mod` 2) 
       = 1000 * repBinario 3 + 0 
       = 1000 * (10 * repBinario (3 `div` 2) + 3 `mod` 2) 
       = 10000 * repBinario 1 + 1000 * 1 
       = 10000 (10 * repBinario (1 `div` 2) + 1 `mod` 2) + 1000 
       = 10000 (10 * repBinario 0 + 1) + 1000 
       = 10000 (10 * 0 + 1) + 1000 
       = 10000 * 1 + 1000 
       = 11000 

trong các bước này, tôi chỉ đánh giá hàm theo định nghĩa của nó và sử dụng thực tế là số nguyên/phép nhân tuân thủ luật phân phối.