有一种有效的方法将一个一元数字转换为二进制数字吗？ [英] Is there any efficient way to convert an unary number to a binary number?

问题描述

这些数据类型分别表示一元和二元自然数：

 数据UNat = Succ UNat |零
数据BNat =一个BNat |零BNat |结束
 
 u0 =零
 u1 = Succ Zero 
 u2 = Succ（Succ Zero）
 u3 = Succ（Succ（Succ Zero））
 u4 = Succ（Succ（Succ（Succ Zero）））
 
 b0 = End // 0 
 b1 = One End // 1 
 b2 = One（Zero End）// 10 
 b3 =一个（一个结束）// 11 
 b4 =一个（零（零结束））// 100 
 
（或者，可以使用`Zero End'作为b1，`一端'为b2，`零（零端）'为b3 ...）
  

我的问题是：是否有任何方法来实现该功能：

  toBNat :: UNat  - > BNat 
  

在 O（N） ，只通过UNat一次？

解决方案

要增加一个二进制数字，您必须在数字的末尾和前面的所有数字。该操作的成本与输入结束时的1的数量成正比（为此，您应该将数字表示为从右至左的列表，例如，列表[1; 0; 1; 1]代码为13） 。

设n（n）是n的结尾的数字：

  a（n）= 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4，... 
  

并让

   / pre> 
 
 
是两个幂的2之和的元素之和。你应该能够说服自己s（k + 1）= 2 * s（k）+ 1（s（0）= 1）注意到
 
 pre $  a（2 ^（k + 1））... ，（2 ^（k + 2） -  1）
  

是通过连接

（2 ^ k）+1，...，a（2 ^（k + 1） - 1）和a（2 ^（k + 1） k），...，a（2 ^（k + 1） - 1）

，作为几何级数，s（k）= 2 ^ k - 1。

现在增加N次的成本a数量应该与

  a（0）+ a（1）+ ... + a（N）$ b $成比例b = s（0）+ s（1）+ s（2）+ ... + s（log（N））
 = 2 ^ 0  -  1 + 2 ^ 1 -1 + 2 ^ 2-1 + ... + 2 ^ log（N） -  1 
 = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ log（N） -  log（N） -  1 
 = 2 ^（log（N）+1） -  1  -  log（N）-1 = 2N  -  log（N） -  2 
  

因此，如果你注意从右到左表示你的数字，那么朴素算法是线性的（注意，如果你真的需要你的数字，你可以执行列表反转并保持线性反过来）。

Let those datatypes represent unary and binary natural numbers, respectively:

data UNat = Succ UNat | Zero
data BNat = One BNat | Zero BNat | End

u0 = Zero
u1 = Succ Zero
u2 = Succ (Succ Zero)
u3 = Succ (Succ (Succ Zero))
u4 = Succ (Succ (Succ (Succ Zero)))

b0 = End                   //   0
b1 = One End               //   1
b2 = One (Zero End)        //  10
b3 = One (One End)         //  11
b4 = One (Zero (Zero End)) // 100

(Alternatively, one could use `Zero End` as b1, `One End` as b2, `Zero (Zero End)` as b3...)

My question is: is there any way to implement the function:

toBNat :: UNat -> BNat

That works in O(N), doing only one pass through UNat?

解决方案

To increment a binary digit, you have to flip the first zero at the end of your number and all the ones preceding it. The cost of this operation is proportional to the number of 1 at the end of your input (for this your should represent number as right-to-left list, eg. the list [1;0;1;1] codes for 13).

Let a(n) be the number of 1 at the end of n:

a(n) = 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...

and let

s(k) = a(2^k) + a(2^k+1) + ... + a(2^(k+1)-1) 

be the sum of elements between two powers of 2. You should be able to convince yourself that s(k+1)=2*s(k) + 1 (with s(0) = 1) by noticing that

    a(2^(k+1)) ..., a(2^(k+2) - 1) 

is obtained by concatenating

    a(2^k) + 1, ..., a(2^(k+1) - 1) and   a(2^k), ..., a(2^(k+1) - 1)

And therefore, as a geometric series, s(k) = 2^k - 1.

Now the cost of incrementing N times a number should be proportional to

    a(0) + a(1) + ... + a(N)
  = s(0) + s(1) + s(2)  + ... + s(log(N)) 
  = 2^0 - 1 + 2^1 -1 + 2^2-1 + ... + 2^log(N) - 1
  = 2^0 + 2^1 + 2^2 + ... + 2^log(N) - log(N) - 1
  = 2^(log(N) + 1) - 1 - log(N) - 1 = 2N - log(N) - 2

Therefore, if you take care of representing your numbers from right-to-left, then the naive algorithm is linear (note that you can perform to list reversal and stay linear if you really need your numbers the other way around).

这篇关于有一种有效的方法将一个一元数字转换为二进制数字吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！