The Zen of Python, by Tim Peters

=============

由于自己对新知识的好奇,2014年被一位朋友吸引,当时遇到他时,他是在坚持用python进行实现自己的功能。同时用的是vim进行编写,而之前我一直是用
IDE
,2015年初,我开始了解python,首先我接触到的就是

    
import this

The Zen of Python

- **Python的原则**

Beautiful is better than ugly.

- **优美胜于丑陋(Python 以编写优美的代码为目标)**

Explicit is better than implicit.

- **明了胜于晦涩(优美的代码应当是明了的,命名规范,风格相似)**

Simple is better than complex.

- **简洁胜于复杂(优美的代码应当是简洁的,不要有复杂的内部实现)**

Complex is better than complicated.

- **复杂胜于凌乱(如果复杂不可避免,那代码间也不能有难懂的关系,要保持接口简洁)**

Flat is better than nested.

- **扁平胜于嵌套(优美的代码应当是扁平的,不能有太多的嵌套) **

Sparse is better than dense.

- **间隔胜于紧凑(优美的代码有适当的间隔,不要奢望一行代码解决问题)**

Readability counts.

- **可读性很重要(优美的代码是可读的)**

Special cases aren't special enough to break the rules.

- **即便假借特例的实用性之名,也不可违背这些规则(这些规则至高无上)**

Although practicality beats purity.

Errors should never pass silently.

- **不要包容所有错误,除非你确定需要这样做(精准地捕获异常,不写 except:pass 风格的代码)**

Unless explicitly silenced.

- **而是尽量找一种,最好是唯一一种明显的解决方案(如果不确定,就用穷举法)**

In the face of ambiguity, refuse the temptation to guess.

- **当存在多种可能,不要尝试去猜测**

There should be one-- and preferably only one --obvious way to do it.

- **而是尽量找一种,最好是唯一一种明显的解决方案(如果不确定,就用穷举法)**

Although that way may not be obvious at first unless you're Dutch.

- **虽然这并不容易,因为你不是 Python 之父(这里的 Dutch 是指 Guido )**

Now is better than never.

Although never is often better than *right* now.

- **做也许好过不做,但不假思索就动手还不如不做(动手之前要细思量) **

If the implementation is hard to explain, it's a bad idea.

If the implementation is easy to explain, it may be a good idea.

- **如果你无法向人描述你的方案,那肯定不是一个好方案;反之亦然(方案测评标准)**

Namespaces are one honking great idea -- let's do more of those!

- **命名空间是一种绝妙的理念,我们应当多加利用(倡导与号召)**



---- by Tim Peters


  • python 也用了一段时间,感觉他和javascript很像,但是只是感觉,具体哪里像,后面我会归档一下,同时也是为自己理清思路。
  • 她与java的区别,我目前感觉两种语言,只是语法上的不同,没有感觉到非常大的差别,我也会单独整理一份这两个语言的差别。但自己学习。

POI设置表格自动换行

在开发过程中有些同学遇到需要表格自动换行,其实poi不设置高度,设置WrapText即可

`        <dependency>
<groupId>org.apache.poi</groupId>
<artifactId>poi</artifactId>
<version>3.15</version>
<scope>compile</scope>
</dependency>

代码片断参考

@Test
public void xssfWrite() throws Exception {

Workbook finalWb = new XSSFWorkbook();
XSSFSheet sheet = (XSSFSheet) finalWb.createSheet(System.currentTimeMillis()+"");
sheet.setDefaultColumnWidth(20);
SheetContent content=new SheetContent();
content.setHeaders(Lists.newArrayList("title","content"));
Map<String, Object> temp = Maps.newHashMap();
temp.put("title","jdk8之前为空判断使业务代码读起来比较费劲,对整体业务逻辑的理解增加困惑;" + "jdk8支持了 Optional 之后 ,使用我们可以非常轻松的将原本一大块的判断代码块变成一句话;");
temp.put("content","左侧是自动换行");
Map<String, Object> temp2 = Maps.newHashMap();
temp2.put("title","POIFSFileSystem fs = new POIFSFileSystem(new FileInputStream(filePath));");
temp2.put("content","左侧是自动换行");
content.setValues(Lists.newArrayList(temp,temp2));
writeSheet(sheet,content);
FileOutputStream bos=new FileOutputStream("异常数据.xlsx");
finalWb.write(bos);


}
private void writeSheet(XSSFSheet sheet, SheetContent content) {
Set<Object> last= Sets.newHashSet();
for (int i = 0; i < content.getHeaders().size(); i++) {
writeCell(sheet,0,i,null,content.getHeaders().get(i));
}

int row=0;
for (int i = 0; i < content.getValues().size(); i++) {
Map<String, Object> contents=content.getValues().get(i);
ArrayList<Object> temp = new ArrayList<>(contents.values());
last.add((temp.get(0)));
row++;
for (int i1 = 0; i1 < temp.size(); i1++) {
Object item=temp.get(i1);
if(item instanceof Double){
if(((Double) item).intValue()==((Double) item).doubleValue()){
item=((Double) item).intValue();
}
}
writeCell(sheet,row,i1,null,item);
}
}
System.out.println(last.size()+","+last);

}

private void writeCell(XSSFSheet sheet, int r, int l, Color color, Object value) {
XSSFRow row = sheet.getRow(r);
if (row == null) {
row = sheet.createRow(r);
}
XSSFCell cell = row.getCell(l);
if (cell == null) {
cell = row.createCell(l);
}
cell.setCellValue(value.toString());
XSSFCellStyle style = sheet.getWorkbook().createCellStyle();
if (color == null) {
color = new java.awt.Color(162, 187, 185);
}
style.setFillForegroundColor(new XSSFColor(color));
style.setVerticalAlignment(VerticalAlignment.TOP);
style.setFillPattern(CellStyle.SOLID_FOREGROUND);
style.setWrapText(true);
cell.setCellStyle(style);
}

@Data
public static class SheetContent {
private String sheetName;
private List<Object> headers= Lists.newArrayList();
private List<Map<String,Object>> values=Lists.newArrayList();
public void addValue(List<Object> cells){
Map<String,Object> value=Maps.newLinkedHashMap();
for (int i = 0; i < headers.size(); i++) {
value.put(headers.get(i)+"",cells.get(i));
}
values.add(value);
}
}

jdk_null有关判断--Optional

jdk8之前为空判断使业务代码读起来比较费劲,对整体业务逻辑的理解增加困惑;
jdk8支持了 Optional 之后 ,使用我们可以非常轻松的将原本一大块的判断代码块变成一句话;

正常的判空优化效果

Optional.ofNullable(null).orElse("default")

从对象中取值时

String userName=null;
User user=null;
if(Objects.isNull(user)){
userName="username is null";
}else{
userName=user.getName();
}

优化后

userName=Optional.ofNullable(user).map((temp)->temp.getName()).orElse("default");



userName=Optional.ofNullable(user).flatMap(user1 -> Optional.ofNullable(user1.getName())).orElse("happy");

redis

一. redis 实现原理

五种类型的键的底层实现数据结构

具体命令可参考命令

  1. SDS( simple dynamic string) 简单动态字符串

    struct sdshdr{
    int len;
    int free;
    char buf[];
    }
  2. 链表

    typedef struct listNode{
    struct listNode *prev;
    struct listNode *next;
    void *value;
    }listNode;

    typedef struct list{
    listNode *head;
    listNode *tail;
    unsigned long len;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr,void *key);
    }
  3. 字典

    Redis 的字典使用哈希表作为底层实现,一个哈希敷衍里面可以有多个节点,每个节点就保存了字典中的一个键值对;

    新添加一个键值对到字典里时,程序需要先根据键值对的键计算出哈希值和索引值,然后根据索引值,将包含新键值对的哈希表节点放到哈希表数组的指定索引上面.当有两个或以上数量的键被分配到哈希数组的同一个索引上面时,我们称为冲突.这里使用链地址法解决键冲突.

    • 哈希表

      typedef struct dictht{
      dictEntry **table;
      unsigned long size;
      unsigned long sizemask;
      unsigned long used;
      }

      sizemask 值和哈希值一起决定一个键应该被放到table数组的哪个索引上面.

    • 哈希表节点

      typedef struct dictEntry{
      void *key;
      union{
      void *val;
      uint64_tu64;
      int64_ts64;
      } v;
      struct dictEntry *next; //解决键冲突的问题
      } dictEntry;
    • 字典

      typedef struct dict{
      dictType *type; //类型特定函数
      void *privdata;//私有数据
      dictht ht[2];//哈希表
      int trehashidx;//索引
      } dict;
    • rehash(实际过程,是渐进式的)

      当哈希表中键值的数量太多或太少时,为了让哈希表的负载因子维持在一个合理的范围之内,程序需要对哈希表的大小进行相应的扩展或者收缩.

      1. 为字段的ht[1]哈希表分配空间,这个空间大小取决于要执行的操作,以及ht[0]当前包含的键值对数量

        1. 如果是扩展操作,那么大小为第一个大于等于ht[0].used*2的2的n次方
        2. 如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方
      2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面:rehash指重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上

      3. 将ht[0]释放空间,同时将ht[0]和ht[1]换位置

        何时进行扩展和收缩
        负载因子= ht[0].used(已保存的节点数量)/哈希表的大小

        当负载因子大于 5 (待确认),或<0.1 时

  4. 跳跃表

    skiplist 是一种有序的数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的.
    redis在以下两个地方用到了跳跃表:

    1. 有序集合键 zset
    2. 在集群节点中用途内部数据结构
  5. 整数集合

    intset 是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现.

    127.0.0.1:6379> SADD numbers 1 3 5 6 7
    (integer) 5

    127.0.0.1:6379> OBJECT ENCODING numbers
    "intset"

    127.0.0.1:6379> sadd numbers 0943890384093845903845094385
    (integer) 1

    127.0.0.1:6379> smembers numbers
    1) "3"
    2) "0943890384093845903845094385"
    3) "7"
    4) "2"
    5) "6"
    6) "1"
    7) "9"
    8) "5"

    127.0.0.1:6379> OBJECT ENCODING numbers
    "hashtable"

    每当我们要将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有的所有元素的类型都要长时,整数集合需要先进行升级,然后才能将新元素添加到整数集合里面,请记住,这里不会降级的

    其是Redis保存整数值的集合抽象数据结构,它可以保存int16_t,int32_t,int64_t的整数值,并且保证集合中不会出现重复元素.

    typedef struct intset{
    uint32_t encoding;//编码方式 INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64
    uint32_t length;//集合包含的元素数量
    int8_t contents[]; //保存元素的数组,数组中按值的大小从小到大有序排列,并且数组中不包含任何重复项;其真正的类型取决于encoding属性的值:
    }

  6. 压缩列表
    ziplist,是列表键和哈希键的底层实现之一.当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现.

    127.0.0.1:6379> rpush kdf djf f df d f d f "sdf"
    (integer) 8

    127.0.0.1:6379> OBJECT ENCODING kdf
    "ziplist"

    压缩列表是为了节约内存而开发的,是由一系列特殊的连续内存块组成的顺序型数据结构.一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数值.

对象处理机制以及数据库的实现原理

  1. 导入

    1. Redis 基于这些数据结构创建一个对象系统,其包含 字符串,列表对象,哈希对象,集合对象和有序集合对象 五种类型的对象,每种对象都至少一种我们前面所介绍的数据结构.
    2. 使用对象的好处,我们可以针对不同的使用场景,为对象设置多种不同的数据结构pugmww而优化对象在不同场景下的使用效率.
    3. 对象系统基于引用计数技术的内存回收机制,当程序不再使用某个对象的时候,这个对象所战胜的内存就会被自动释放;另外,Redis还通过引用计数技术实现了对象共享机制,这一机制可以在适当的条件下,通过让多个数据库键共享同一个对象来节约内存.
    4. 对象带有访问时间记录信息,该信息可以用于计算数据库的空转时长 ,在服务器启用了maxmemory功能的情况下,空转时长较大的那些键可能会优先被服务器删除.
  2. 对象的类型和编码 type

    Redis使用对象来表示数据库中的键值,每次我们在库中新创建一个键值对时,我们至少会创建两个对象,一个是键对象,另一个是值对象.

    127.0.0.1:6379> set name aaron
    OK
    127.0.0.1:6379> get name
    "aaron"
    127.0.0.1:6379> OBJECT ENCODING name
    "embstr"
    127.0.0.1:6379> type name
    string
    127.0.0.1:6379> OBJECT idletime name
    (integer) 46


    每一个对象都由一个redisObject结构表示,该结构中和保存数据有关的三个属性分别是type属性,encoding属性和ptr属性:

    typedef struct redisObject{
    unsigned type:4;
    unsigned encoding:4;
    void *ptr;//每日向底层实现数据结构的指针
    int refcount;//引用计数
    unsigned lru:22;//该对象最后一次被访问的时间
    }robj;

    type记录了对象的类型,这个属性的值有 string,list,hash,set,zset

  3. 编码和底层实现 OBJECT ENCODING
    对象的ptr指针指向对象的底层实现数据结构,而这些数据结构由对象的encoding属性决定.也就是说这个对象使用了什么数据结构作为对象的底层实现,这个属性值可以是

    int (long 类型)
    embstr (embstr编码的简单动态字符串)
    raw (简单动态字符串)
    ht (字典)
    linkedlist (双端链表)
    ziplist (压缩链表)
    intset (整数集合)
    skiplist (跳跃链表和字典)

    每种类型对象都至少使用了两种不同的编码.

    string int/embstr/raw
    list ziplist/linkedlist
    hash ziplist/ht
    set intset/ht
    zset ziplist/skiplist
  4. 数据共享 只共享0-9999的字符串对象

    127.0.0.1:6379> SET a 100
    OK
    127.0.0.1:6379> OBJECT refcount a
    (integer) 2
    127.0.0.1:6379> OBJECT refcount a
    (integer) 2
    127.0.0.1:6379> SET b 100
    OK
    127.0.0.1:6379> OBJECT refcount a
    (integer) 3
    127.0.0.1:6379>

单机数据库的实现

  1. 在redisServer结构的db数组中,每个redisDb 结构代表一个数据库,启动服务器时,服务器会根据dbnum来决定应该创建多少个数据库:

    struct redisServer{
    ...
    redisDb *db;
    int dbnum;
    ...
    }redisClient

    客户端可以根据命令select来进行切换目标数据库

  2. 数据库键空间

    是一个键值对数据库服务器,其中每个数据库都由一个redisDb结构表示,其中redisDb结构的dict字典保存了数据库中的所有键值对,我们称这个字典为 键空间
    typedef struct redisDb{
    dict *dict;
    dict *expires; key 是对象,value 是过期时间
    }redisDb

  3. 设置生存时间或过期时间

    127.0.0.1:6379> set name wansong
    OK
    127.0.0.1:6379> expire name 10
    (integer) 1
    127.0.0.1:6379> get name
    "wansong"
    127.0.0.1:6379> get name
    (nil)

  4. 数据库通知
    2.8 新版本中增加的功能,可以通过订阅给它的频道或者模式,来获知数据库中键的变化.及数据库中命令的执行情况.

RDB 持久化和 AOF 持久化的实现原理

RDB持久化功能,可以将Redis在内存中的数据库状态保存到磁盘里面,避免数据意外丢失.也可以根据服务器配置选项定期执行.
该功能可以将某个时间点上的数据库状态保存到一个RDB文件中.该文件是一个经过压缩的二进制文件,通过该文件可以还原生成RDB文件时的数据库状态.

  1. RDB文件的创建与载入

    save 命令会阻塞Redis服务器进程,直到RDB文件创建完毕为止,在服务器进程阻塞期间,服务器不处理任务命令请求.

    bgsave background saving started 该命令会派生出一个子进程,然后由子进程负责创建RDB文件,服务器进程继续处理命令请求

    创建文件的实际工作由rdbSave函数完成,save和bgsave命令会以不同的方式调用这个函数.

    RDB文件的载入是自动的,当程序启动时会自动载入,另外注意AOF文件的更新频率通常比RDB高,所以:

    1. 如果服务器开启了AOF持久化功能,那么服务器会优先使用AOF文件还原数据库状态

    2. 只有在AOF持久化功能处于关闭状态时,服务器才会使用RDB文件来还原数据库状态.

      载入RDB文件的实际工作由rdbLoad函数完成;文件载入时服务器处于阻塞状态.

  2. 自动间隔性保存

    可以通过save选项设置多个保存条件,但只要其中任意一个条件被满足,服务器就会执行bgsave.

    save 900 1 服务器900秒之内,对数据库进行至少一次修改,就进行bgsave

事件

Redis 基于 Reactor模式开发的网络事件处理器,称作 文件事件处理器 (File Event Handler)

  1. 使用I/O多路复用程序来同时监听多个套接字,并根据目前执行的任务来为套接字关联不同的事件
  2. 当被监听的套接字准备好执行连接应答,读取,写入,关闭 等操作时,与其对应的文件事件就会产生,这时1中注册好的事件处理器就来进行处理这些事件

时间事件 id/when/handlers

  1. 定时事件
  2. 周期性事件

事务实现原理 ACID

ServerCron函数

服务器 默认每100毫秒执行一次

  1. 更新服务器时间缓存
  2. 更新LRU时钟(如 Redis对象都会有一个LRU属性,这个属性保存了对象最后一次被命令访问的时间)
  3. 更新服务器每秒执行命令的次数(INFO status)
  4. 更新服务器内存峰值记录
  5. 处理SIGTERM信号 每次运行时,程序会对服务器状态的shutdown_asap属性进行检查,看是否要关闭服务器
  6. 管理客户端资源: 已超时 或 是否清理输出缓冲区
  7. 管理数据库资源: 删除过期键,并在需要时 对字典进行收缩操作
  8. 检查持久化操作的运行状态
  9. 将AOF缓冲区的内容写入到AOF文件
  10. 关闭异步客户端
  11. 增加cronloops计数器的值

初始化过程

初始化服务器状态结构,载入配置选项,还原数据库状态,执行事件循环

订阅与发布实现原理

Lua 脚本功能的实现原理。

SORT 命令的实现原理。

慢查询日志的实现原理。 打开慢查询,查看日期 SLOWLOG GET

高并发如何做到

虽是单线程单进行,但 使用I/O多路复用(select/epoll,evport,kqueue)程序来同时监听多个套接字 的方式来处理命令请求,并与多个客户端进行通信.

二. redis 主要关注点

redis 为什么是单线程

redis 过期索引是如何做到的

  1. redis 的存储结构

  2. 删除策略

    * 定时删除:在设置键的过期时间的同时,创建一个定时器,让定时器在键的过期时间来临时,立即对键执行删除操作(对内存友好,最及时)
    * 定期删除:每一段时间,进行数据库过期索引的扫瞄,将已经过期的键 进行删除; 至于删除多少过期键和检查哪些数据库,都由算法决定
    * 惰性删除: 每次取键时,校验一下是否过期,若已经过期 就进行删除

    其实最终使用的是 定期和惰性 两个策略 配合实现

    redis 服务器配置

    redis 有哪些功能

    redis 如何Failover()

    哨兵(Sentinel)和复制(Replication
    Sentinel可以管理多个Redis服务器,它提供了监控,提醒以及自动的故障转移的功能;Replication则是负责让一个Redis服务器可以配备多个备份的服务器

redis 目前流程的实施架构有哪些

  1. 哨兵Sentinel,复制(replication)
  2. 集群(cluster)

三. redis 应用场景

参考

  1. Redis设计与实现

微服务相关概念

服务治理基本概念

  1. 服务的伸缩控制
  2. 身份验证与授权 *
  3. 服务注册与发现 *
  4. 反向代理与负载均衡
  5. 路由控制 *
  6. 流量切换 *
  7. 日志管理 *
  8. 性能度量、监控与调优 *
  9. 分布式跟踪 *
  10. 过载保护 *
  11. 服务降级 *
  12. 服务部署与版本升级策略支持 *
  13. 错误处理 *
  14. 国际化

服务的伸缩控制

身份验证与授权

服务注册与发现

  1. dubbo zookeeper

反向代理与负载均衡

  1. vertx
  2. nginx

二分法查找及扩展

二分法查找

给一个有序数组,查找出k所在位置

/**
* @author Aaron
* @since 6.2
*/
public class TheFirstLessThan100 {
public static int find(int[] array, int value) {

int low = 0;
int high = array.length - 1;
int count = 0;
while (low <= high) {
int middle = (low + high) >>> 1;
int middleValue = array[middle];
count++;
if (middleValue < value) {
low = middle + 1;
} else if (middleValue > value) {
high = middle - 1;
} else {
System.out.printf("times:%d,index:%d,value:%d\n", count, middle, value);
return middle;
}
}
return -1;
}


public static void main(String[] args) {
int[] array = new int[]{1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 8, 9, 10, 14, 17, 19, 20};
for (int i = 0; i < array.length; i++) {
int index = find(array, array[i]);
}
}
}

查出第一个大于N的位置

从有序的数组中,找出第一个大于N的数字的位置


public static int findFirstBigIndex(int[] array, int value) {

int lastBigIndex=-1;

int low = 0;
int high = array.length - 1;
int count = 0;

while (low <= high) {
int middle = (low + high) >>> 1;
int middleValue = array[middle];
count++;
if (middleValue <= value) {
low = middle + 1;
} else if (middleValue > value) {
high = middle - 1;
lastBigIndex=middle;
System.out.printf("times:%d,index:%d,value:%d,middle:%d\n", count, middle, value,middleValue);
}
}
return lastBigIndex;
}



public static int findFirstBigIndex1(int[] array, int value) {

int low = 0;
int high = array.length - 1;
int count = 0;

while (low <= high) {
int middle = (low + high) >>> 1;
int middleValue = array[middle];
count++;
if (middleValue <= value) {
low = middle + 1;
} else if (middleValue > value) {
high = middle - 1;
System.out.printf("times:%d,index:%d,value:%d,middle:%d\n", count, middle, value,middleValue);
}
}
return low;
}

public static void main(String[] args) {
int[] array = new int[]{1, 2, 3, 4, 5, 6, 8, 9, 10, 14, 17, 19, 20,21,22,34,324,546};
for (int i = 0; i < array.length; i++) {
int index = findFirstBigIndex1(array, i);
int index2 = findFirstBigIndex(array, i);
System.out.println(index+"--"+index2);
}
}

微信头像九宫格算法

分别计算1-9个头像在九宫格中的位置


public static List<ImageCell> createMergeCell(int n, int totalWidth) {
int totalRow = (int) Math.ceil(Math.sqrt(n));
int outline = 5;
int width = ((totalWidth - outline) / totalRow);
int border = width / 20;
if (n == 1) {
return Lists.newArrayList(new ImageCell(border, border, width - 2 * border));
}
int lastAloneNum = n % totalRow;
int totalFullRow = n / totalRow;
int lastRow = totalRow - totalFullRow - 1;

int firstStartX = (totalWidth - lastAloneNum * width) / 2;
int firstStartY = lastRow * width;

int otherSpace = (totalWidth - totalRow * width) / 2;
int yOffset = 0;
if (totalRow != totalFullRow + (lastAloneNum != 0 ? 1 : 0)) {
yOffset = -width / 2;
}
List<ImageCell> imageCells = Lists.newArrayList();
for (int i = 0; i < n; i++) {
int x = 0, y = firstStartY;
if (i < lastAloneNum) {
x = firstStartX + i * width;
} else {
x = (i - lastAloneNum) % totalRow * width;
y = firstStartY + ((i - lastAloneNum) / totalRow + 1) * width;
}
imageCells.add(new ImageCell(x + border + otherSpace, y + border + otherSpace + yOffset, width - 2 * border));
}
return imageCells;
}

@Data
@AllArgsConstructor
static class ImageCell {
int x;
int y;
int width;

}

-------------------n=1---------------------
x:7,y:7,width:131




-------------------n=2---------------------
x:6,y:42,width:66
x:78,y:42,width:66




-------------------n=3---------------------
x:45,y:6,width:66
x:6,y:78,width:66
x:78,y:78,width:66




-------------------n=4---------------------
x:6,y:6,width:66
x:78,y:6,width:66
x:6,y:78,width:66
x:78,y:78,width:66




-------------------n=5---------------------
x:32,y:29,width:44
x:80,y:29,width:44
x:5,y:77,width:44
x:53,y:77,width:44
x:101,y:77,width:44




-------------------n=6---------------------
x:5,y:29,width:44
x:53,y:29,width:44
x:101,y:29,width:44
x:5,y:77,width:44
x:53,y:77,width:44
x:101,y:77,width:44




-------------------n=7---------------------
x:56,y:5,width:44
x:5,y:53,width:44
x:53,y:53,width:44
x:101,y:53,width:44
x:5,y:101,width:44
x:53,y:101,width:44
x:101,y:101,width:44




-------------------n=8---------------------
x:32,y:5,width:44
x:80,y:5,width:44
x:5,y:53,width:44
x:53,y:53,width:44
x:101,y:53,width:44
x:5,y:101,width:44
x:53,y:101,width:44
x:101,y:101,width:44




-------------------n=9---------------------
x:5,y:5,width:44
x:53,y:5,width:44
x:101,y:5,width:44
x:5,y:53,width:44
x:53,y:53,width:44
x:101,y:53,width:44
x:5,y:101,width:44
x:53,y:101,width:44
x:101,y:101,width:44

取一个数字二进制中1的个数

  1. 二进制中1的个数

     
    int countBits(int n) {
    int count=0 ;
    while (n>0) {
    count++ ;
    n &= (n - 1) ;
    }
    return count ;
    }
    复杂度: < log2n
  2. 方案二

     
    /**
    * Returns the number of one-bits in the two's complement binary
    * representation of the specified {@code int} value. This function is
    * sometimes referred to as the <i>population count</i>.
    *
    * @param i the value whose bits are to be counted
    * @return the number of one-bits in the two's complement binary
    * representation of the specified {@code int} value.
    * @since 1.5
    */
    public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
    }

    复杂度: 1
  3. 方案三

     
    public static int countBit1(int n) {
    int count=0 ;
    int temp=1;
    while (temp<=n) {
    if((temp&n)>0){
    count++ ;
    }
    temp<<=1;
    }
    return count ;
    }

扩展

  1. 给定一个数字n计算从1到n每一个数字的二进制中包含1的个数
        
public static int[] countBits(int num) {
int[] ret = new int[num + 1];

for (int i = 0; i <= num; i++) {
int div = i / 2;
int mod = i % 2;

if (mod == 1) {
ret[i] = ret[div] + 1;
} else {
ret[i] = ret[div];
}
}
return ret;
}