文档章节

把整数转换成2的n次方的和数组

hell0cat
 hell0cat
发布于 2016/09/04 00:31
字数 702
阅读 74
收藏 1

大概这样:125 => [1, 4, 8, 16, 32, 64]

写几种实现: Ruby:

2.3.1 :022 > 125.to_s(2).reverse.chars.map.with_index{|b, i| b.to_i.zero? ? nil : 2**i}.compact 
 => [1, 4, 8, 16, 32, 64] 

或者:

2.3.1 :028 > 125.to_s(2).reverse.chars.map.with_index{|b,i| b.to_i*2**i}.reject(&:zero?) 
 => [1, 4, 8, 16, 32, 64] 

Haskell: Haskell的整数转成二进制序列比较麻烦,先写一个函数来实现:

import Numeric (showHex, showIntAtBase)
import Data.Char (intToDigit)

bits :: Int -> [Int]
bits x = map (\n -> read [n]::Int) $ showIntAtBase 2 intToDigit x ""
main = do
    print $ bits 125

bits 函数用来将一个整数转换成 二进制的整数 数组 如 bits 125 => [1,1,1,1,1,0,1]

第二步,构造2的n次方序列[1,2,4,8,16...] 然后 将n次方序列和 反转后的二进制序列对应位相乘,最后过滤掉0。

main = do
    print . filter (/=0) . zipWith (*) [ 2^n | n <- [0..] ] . reverse $ bits 125

Haskell利用位移算法实现,依赖Data.Bits包里的 位与右移 函数:

import Data.Bits

bits2 :: Int -> [Int]
bits2 x | x <=0         = []
        | otherwise     = bits2 (shiftR x 1) ++ [x .&. 1]
--  bits2 函数即通过位移实现二进制List,由于需要reverse,所以下面实际用到的bits稍微修改。
--  bits2 返回的是二进制序列的倒序,避免里reverse一次。
        
bitsList :: Int -> [Int]
bitsList x = filter (/=0) . zipWith (*) [2^n | n<-[0..] ] $ bits x
            where 
                bits n  | n <=0 = []
                        | otherwise = n .&. 1 : bits (shiftR n 1)

main = do
    print $ bitsList 125    
=> [1,4,8,16,32,64]

这样的实现方法似乎更加Haskell,

Js实现:

> (125).toString(2).split('').reverse().map((e,i) => parseInt(e) * Math.pow(2,i)).filter( e => e>0 )
[ 1, 4, 8, 16, 32, 64 ]

Js位移方法实现,每次右移1位,同时判断末尾是否位1,为1则,加入。

function bits(n) {
  var result = [];
  var m = 0;
  while (n > 0) {
    if (n & 1) {
      result.push(Math.pow(2, m));
    }
    m++;
    n >>= 1;
  }
  return result;
}

console.log(bits(125));
> [ 1, 4, 8, 16, 32, 64 ]

或者写成for,简单一些

function bits(n) {
  var result = [];
  for (var m = 0; n > 0; m++, n >>= 1) {
    if (n & 1) {
      result.push(Math.pow(2, m)); // es7: 2**m
    }
  }
  return result;
}

es7支持 指数运算符 **,es6还不支持,chrome浏览器已经支持,更加简化。

Julia

# 复合函数,(Julia >=0.6版本,已经内置该函数,so easy!)
∘(f::Function, g::Function) = x -> f(g(x))

function binaryLists(n::Int)
  b = [x for x in lstrip(bits(n), '0')]
  filter(x->x>0, map(*, [2^y for y=0:length(b)-1], map(parse ∘ string, reverse(b))))
end

print(binaryLists(125))

=> [1,4,8,16,32,64]

julia在这个问题上处理有些复杂,无法轻松构造出一个无限列表,map针对多个List参数时候,必须保证所有List长度一致,这点区别于Haskell的 zipWith,zipWith两个列表按最短的为准,忽略多余的。为了简化代码定义了一个复合函数(),这样就不用写 x-> parse(string(x)) julia支持两个List直接用 list1 .* list2 来相乘对应位,可以替换 map(*, list1, list2)

function binaryLists(n::Int)
  b = [x for x in lstrip(bits(n), '0')]
  filter(x->x>0, [2^y for y=0:length(b)-1] .* map(parse ∘ string, reverse(b)))
end

适当化简一些。

© 著作权归作者所有

共有 人打赏支持
上一篇: Image
下一篇: PHP扩展开发
hell0cat
粉丝 37
博文 48
码字总数 24082
作品 0
徐汇
程序员
私信 提问
二进制,十进制,八进制,十六进制

一、 进制的概念在计算机语言中常用的进制有二进制、八进制、十进制和十六进制,十进制是最主要的表达形式。 对于进制,有两个基本的概念:基数和运算规则。基数:基数是指一种进制中组成的基...

西鼠
2017/12/11
0
0
Java集合-HashMap扰动函数

上一篇文章HashMap内部结构提到了 HashMap 有一个扰动函数,来判断元素落在数组的位置。下面通过具体的例子说明。 说明 get 方法如何确定key在数组中的位置,先通过 hash(key) 再通过 tab[(n...

gaob2001
2018/10/29
0
0
简单的数据进制转化

1.十进制转化为二进制除以2,求余数;小数部分成2,求整数部分 2.二进制转十进制,从右开始每一个二进制数乘以2的n次方(n从0开始)eg:01=》2的0次方+0的2的1次方=1 注释:三位的二进制表示...

月亮1987
2015/05/20
0
0
剑指offer java版(一)

二维数组中的查找 问题描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数...

Android机动车
前天
0
0
[编程题]进制转换

1、题目内容 [编程题]进制转换 2、题目解析 方法1:将十六进制的数值字符串转换成十进制字符串,用Integer类的 public static int parseInt(String s,int radix) throws NumberFormatExcept...

笨拙的小Q
2016/04/22
267
0

没有更多内容

加载失败,请刷新页面

加载更多

记录replugin使用的一个坑

反复编译插件放入宿主中,一直出现如下错误: android.content.res.Resources$NotFoundException: Resource ID #0x7f050000 type #0x5 is not valid 回滚代码,重启AS还是出错。最终发现将宿...

Gemini-Lin
今天
1
0
Vert.x系列(二)--EventBusImpl源码分析

前言:Vert.x 实现了2种完成不同的eventBus: EventBusImpl(A local event bus implementation)和 它的子类 ClusteredEventBus(An event bus implementation that clusters with other Ve......

冷基
今天
1
0
Perl - 获取文件项目

参考:http://www.runoob.com/perl/perl-directories.html 下面返回JSON格式的文件列表 #!/usr/bin/perluse strict;use warnings;use utf8;use feature ':5.26';require Fi......

wffger
昨天
2
0
vue组件系列3、查询下载

直接源码,虽然样式样式不好看,逻辑也不是最优,但是可以留作纪念。毕竟以后类似的功能只需要优化就可以了,不用每次都重头开始。。。 <template> <div class="pre_upload"> <div ...

轻轻的往前走
昨天
2
0
java浅复制和深复制

之前写了数组的复制,所以这里继续总结一下浅复制和深复制。 浅拷贝:对基本数据类型进行值传递,对引用数据类型进行引用传递般的拷贝。 深拷贝:对基本数据类型进行值传递,对引用数据类型,...

woshixin
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部