之前一直使用的是Material Design的图标库，下载下来以后直接放入了对应文件夹，什么尺寸对应什么dpi都没有仔细研究过。

最近在Toolbar上添加几个不是MD图标库内的图标时发现，放入的图标在显示时有时候感觉被放大了，有时候又显得模糊。让我对这个图标的尺寸和显示系统产生了好奇，折腾了一番，终于算是基本弄清楚了。

PX、DP和DPI

首先复习一下屏幕像素密度的知识：

1. px：像素点
2. dpi：像素密度，即每英寸像素数
3. dp：屏幕密度独立单位

不同手机的像素密度不同，同px的元素可能有不同的物理尺寸，这不利于多屏幕的适配。因此Android以160dpi（每英寸160像素）为基准定义了单位dp。

即1dp的元素在160dpi的屏幕用1个像素点px显示，在320dpi的屏幕用2px显示，但它们的显示实际物理长度均为1/160＝0.00625英寸。320dpi在同样大小的屏幕内用了更多的像素显示，所以显得更「清晰」。

hdpi、xhdpi、xxhdpi

为了方便换算和显示，Android预定义了一系列的dpi作为基准，例如mdpi定义为160dpi、hdpi定义为240dpi（实际上是一定的范围，但不影响理解）。

我们拿到的图片资源文件是以像素px为单位的，图标的显示却是以dp为单位的。在使用ImageView进行显示时，在规定好图标的长宽后其内容会自动缩放（不同的ScaleType缩放的逻辑不一样），像素过低的图标会显得「不清晰」。

适用于高dpi屏幕的图标可以包含大量细节，在低dpi时直接缩放的话效果可能会出现锯齿、模糊或无法识别其中的元素等情况。为了分别针对不同显示密度的屏幕进行优化，Android在drawable和mipmap文件夹内为不同dpi的屏幕建立了不同的文件夹，在不同的设备上读取相应dpi文件夹内的图片资源进行显示。

Toolbar的icon显示逻辑

与ImageView这样的控件相比，Toolbar显示icon的逻辑就显得比较简单粗暴。在Material Design中，Toolbar的推荐高度为56dp，其中icon的尺寸建议为24dp，那么icon在不同dpi下的实际像素尺寸如下：

这里的问题在于，Toolbar的MenuView在显示时读取图片资源后，不会检查是否应该缩放，而是直接居中显示。那么，如果你的图片资源经过屏幕像素密度换算后不是「恰好」24dp的话，最后显示的效果就会与期望的效果不一致。

例如，xhdpi文件夹存放的应该是48px的icon，如果放入了96px大小的icon的话在Toolbar上就会显得2倍大。反之，在xxxhdpi中放入48px的icon看上去就会额外小。这也是为什么MD图标库中的icon会给mdpi到xxxhdpi一套图标的原因。

解决方案

通常情况下Toolbar的icon都是纯色的png图片，体积非常小。以ic_search_white_24dp.png这个图标为例，mdpi文件夹内的图片大小为396字节，而xxxhdpi文件夹内的图片大小也只有915字节，即使全部使用最大尺寸的图标，对安装包体积的影响也微乎其微。

而且Toolbar的icon都是抽象的图标、细节不多，在低dip的设备上进行缩放时效果并没有太大差别，根据Google发布的设备屏幕尺寸分布情况，hdpi以上的设备也已经占了85%以上。所以如果想要减小安装包体积的话，Toolbar的icon是可以全部只使用一份96px*96px的图片资源，并存放在xxxhdpi中的。

至于其他只在ImageView等控件中显示的资源，如果只有一份的话，放在哪个文件夹内其实是无所谓的。

图标设计规范

根据Material Design的设计规范，Toolbar icon的尺寸应为24dp，触摸响应大小为48dp（Toolbar会自动进行设置），而在icon内部应有一定的留白，一般为2-4dp。因此对于一张96px的icon来说，图片内的四周应有12px左右的边距。

这里推荐一个神器 iconmonstr，在搜索框输入关键词找到想要的icon后，选择png、调整大小为96px、边距12px后，就可以直接下载了。

最近刚好有时间打算好好折腾一下博客的主题，

升级了一下HPSTR，发现它总算用上了SASS，这下魔改起来更方便了。

这次的升级，我在HPSTR 1.7.6的基础上做了一些微调：

功能

1. 文章详情页底部增加了打赏功能
2. 去掉了详情页底部的相关文章模块
3. 左上角弹出菜单中增加了分类列表页面

提升国内访问速度

1. 去掉了托管在Google Fonts上的字体Lato
2. 把jQuery引用的CDN从Google替换成了BootCSS
3. 将统计分析工具从Google Analytics换成了CNZZ
4. 把第三方评论服务商从Disqus换成了国内的友言

视觉效果改进

1. 汉化了默认的大部分英文文本
2. 调整了首页标题的字体字号适应封面图（强迫症）
3. 首页文章列表的题图裁剪、居中并固定高度，把标题放到了题图内
4. Windows下默认字体改为微软雅黑，代码字体换成了Consolas（Mac下是Menlo）
5. 调整了代码块（特别是Java）的高亮颜色，和AS/Intellij的Darcula主题的配色一致

使用Handler.postDelayed()时的疑问

使用handler发送消息时有两种方式，post(Runnable r)和post(Runnable r, long delayMillis)都是将指定Runnable（包装成PostMessage）加入到MessageQueue中，然后Looper不断从MessageQueue中读取Message进行处理。

然而我在使用的时候就一直有一个疑问，类似Looper这种「轮询」的工作方式，如果在每次读取时判断时间，是无论如何都会有误差的。但是在测试中发现Delay的误差并没有大于我使用System.out.println(System.currentTimeMillis())所产生的误差，几乎可以忽略不计，那么Android是怎么做到的呢？

Handler.postDelayed()的调用路径

一步一步跟一下Handler.postDelayed()的调用路径：

1. Handler.postDelayed(Runnable r, long delayMillis)
2. Handler.sendMessageDelayed(getPostMessage(r), delayMillis)
3. Handler.sendMessageAtTime(msg, SystemClock.uptimeMillis() + delayMillis)
4. Handler.enqueueMessage(queue, msg, uptimeMillis)
5. MessageQueue.enqueueMessage(msg, uptimeMillis)

最后发现Handler没有自己处理Delay，而是交给了MessageQueue处理，我们继续跟进去看看MessageQueue又做了什么：

msg.markInUse();
msg.when = when;
Message p = mMessages;
boolean needWake;
if (p == null || when == 0 || when < p.when) {
    // New head, wake up the event queue if blocked.
    msg.next = p;
    mMessages = msg;
    needWake = mBlocked;
} else {
    ...
}

MessageQueue中组织Message的结构就是一个简单的单向链表，只保存了链表头部的引用（果然只是个Queue啊）。在enqueueMessage()的时候把应该执行的时间（上面Hanlder调用路径的第三步延迟已经加上了现有时间，所以叫when）设置到msg里面，并没有进行处理……WTF？

继续跟进去看看Looper是怎么读取MessageQueue的，在loop()方法内：

for (;;) {
    Message msg = queue.next(); // might block
    if (msg == null) {
        // No message indicates that the message queue is quitting.
        return;
    }
    ...
}

原来调用的是MessageQueue.next()，还贴心地注释了这个方法可能会阻塞，点进去看看：

for (;;) {
    if (nextPollTimeoutMillis != 0) {
        Binder.flushPendingCommands();
    }

    nativePollOnce(ptr, nextPollTimeoutMillis);

    synchronized (this) {
        // Try to retrieve the next message.  Return if found.
        final long now = SystemClock.uptimeMillis();
        Message prevMsg = null;
        Message msg = mMessages;
        if (msg != null && msg.target == null) {
            // Stalled by a barrier.  Find the next asynchronous message in the queue.
            do {
                prevMsg = msg;
                msg = msg.next;
            } while (msg != null && !msg.isAsynchronous());
        }
        if (msg != null) {
            if (now < msg.when) {
                // Next message is not ready.  Set a timeout to wake up when it is ready.
                nextPollTimeoutMillis = (int) Math.min(msg.when - now, Integer.MAX_VALUE);
            } else {
                // Got a message.
                mBlocked = false;
                if (prevMsg != null) {
                    prevMsg.next = msg.next;
                } else {
                    mMessages = msg.next;
                }
                msg.next = null;
                if (DEBUG) Log.v(TAG, "Returning message: " + msg);
                msg.markInUse();
                return msg;
            }
        } else {
            // No more messages.
            nextPollTimeoutMillis = -1;
        }
        ...
    }
}

可以看到，在这个方法内，如果头部的这个Message是有延迟而且延迟时间没到的（now < msg.when），会计算一下时间（保存为变量nextPollTimeoutMillis），然后在循环开始的时候判断如果这个Message有延迟，就调用nativePollOnce(ptr, nextPollTimeoutMillis)进行阻塞。nativePollOnce()的作用类似与object.wait()，只不过是使用了Native的方法对这个线程精确时间的唤醒。

精确延时的问题到这里就算是基本解决了，不过我又产生了一个新的疑问：如果Message会阻塞MessageQueue的话，那么先postDelay10秒一个Runnable A，消息队列会一直阻塞，然后我再post一个Runnable B，B岂不是会等A执行完了再执行？正常使用时显然不是这样的，那么问题出在哪呢？

再来一步一步顺一下Looper、Handler、MessageQueue的调用执行逻辑，重新看到MessageQueue.enqueueMessage()的时候发现，似乎刚才遗漏了什么东西：

msg.markInUse();
msg.when = when;
Message p = mMessages;
boolean needWake;
if (p == null || when == 0 || when < p.when) {
    // New head, wake up the event queue if blocked.
    msg.next = p;
    mMessages = msg;
    needWake = mBlocked;
} else {
    ...
}
...
// We can assume mPtr != 0 because mQuitting is false.
if (needWake) {
    nativeWake(mPtr);
}

这个needWake变量和nativeWake()方法似乎是唤醒线程啊？继续看看mBlocked是什么：

Message next() {
    for (;;) {
        ...
        if (msg != null) {
            ...
        } else {
            // Got a message.
            mBlocked = false;
            ...
        }
        ...
    }
    ...
    if (pendingIdleHandlerCount <= 0) {
        // No idle handlers to run.  Loop and wait some more.
        mBlocked = true;
        continue;
    }
    ...
}

就是这里了，在next()方法内部，如果有阻塞（没有消息了或者只有Delay的消息），会把mBlocked这个变量标记为true，在下一个Message进队时会判断这个message的位置，如果在队首就会调用nativeWake()方法唤醒线程！

现在整个调用流程就比较清晰了，以刚刚的问题为例：

1. postDelay()一个10秒钟的Runnable A、消息进队，MessageQueue调用nativePollOnce()阻塞，Looper阻塞；
2. 紧接着post()一个Runnable B、消息进队，判断现在A时间还没到、正在阻塞，把B插入消息队列的头部（A的前面），然后调用nativeWake()方法唤醒线程；
3. MessageQueue.next()方法被唤醒后，重新开始读取消息链表，第一个消息B无延时，直接返回给Looper；
4. Looper处理完这个消息再次调用next()方法，MessageQueue继续读取消息链表，第二个消息A还没到时间，计算一下剩余时间（假如还剩9秒）继续调用nativePollOnce()阻塞；
5. 直到阻塞时间到或者下一次有Message进队；

这样，基本上就能保证Handler.postDelayed()发布的消息能在相对精确的时间被传递给Looper进行处理而又不会阻塞队列了。

Problem: Not So Random

这道题是2016年 Google 校招 APAC Test 的其中一题，也是2016年5月13日Google在北大宣讲会的 Mock Interview Part 的范例题：

There is a certain “random number generator” (RNG) which takes one nonnegative integer as input and generates another nonnegative integer as output. But you know that the RNG is really not very random at all! It uses a fixed number K, and always performs one of the following three operations:

• with probability A/100: return the bitwise AND of the input and K
• with probability B/100: return the bitwise OR of the input and K
• with probability C/100: return the bitwise XOR of the input and K (You may assume that the RNG is truly random in the way that it chooses the operation each time, based on the values of A, B, and C.)

You have N copies of this RNG, and you have arranged them in series such that output from one machine will be the input for the next machine in the series. If > you provide X as an input to the first machine, what will be the expected value of the output of the final machine in the series?

Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with six integers N, X, K, A, B, and C. Respectively, these denote the number of machines, the initial input, the fixed number with which all the bitwise operations will be performed (on every machine), and 100 times the probabilities of the bitwise AND, OR, and XOR operations.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the expected value of the final output. y will be considered correct if it is within an absolute or relative error of 10^-9 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits

1 ≤ T ≤ 50.

0 ≤ A ≤ 100.

0 ≤ B ≤ 100.

0 ≤ C ≤ 100.

A+B+C = 100.

Small dataset

1 ≤ N ≤ 10.

0 ≤ X ≤ 10^4.

0 ≤ K ≤ 10^4.

Large dataset

1 ≤ N ≤ 10^5.

0 ≤ X ≤ 10^9.

0 ≤ K ≤ 10^9.

Sample

In sample test case #1, the final output will be 5 if AND or OR happens and 0 if XOR happens. So the probability of getting 5 is (0.1 + 0.5) and the probability of getting 0 is 0.4. So the expected final output is 5 * 0.6 + 0 * 0.4 = 3.

In sample test case #2, the final output will be 5 with probability 0.72, and 0 otherwise.

位运算

首先理一下题意，把N个RNG串起来，求最后输出结果的期望值。这里很容易注意到，RNG内部的操作（与、或、异或）都是位运算，而一个二进制整数的期望可以用每一位比特的期望乘以所在位的权重计算得到，那么本题就可以简化为只考虑单个比特在系统内的流程来得到单个比特位的期望值。

单个RNG

只考虑一个bit的话，X和K的值组合只有4种，可以列出下面的操作结果表：

注意到这里虽然有A、B、C三种可能性，但是输入和输出都是0和1，是不是可以尝试一下用转移矩阵来做呢？

因为输入是X、输出是0或1，而K是相对固定的、每个RNG的K值都相同。因此，对照上面的结果表分别计算K=0和K=1时的转移矩阵：

k = 0:

[　100 ,　 0　]

[　A　,　B+C　]

k = 1:

[　A　,　B + C　]

[　C　,　A + B　]

（即k=1，输入为0时，输出A%为0、(B+C)%为1；输入为1时，输出C%为0，(A+B)%为1）

这样，我们就将RNG内部当作了一个黑箱，将内部的三种操作简化成了输入输出的转移矩阵。

多个RNG串联

有了单个RNG的转移矩阵，K值又不变，就可以分别计算K=0和K=1时多个RNG的串联结果了，将N-1个矩阵相乘即可。

转移矩阵的定义：

/**
 * 使用double是因为题意要求输出结果精度达到10^-9
 */
private static class Matrix {
    private double a, b, c, d;
    public Matrix(double a, double b, double c, double d) {
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }
}

矩阵的乘法：

 private static Matrix multiply(Matrix m1, Matrix m2) {
    double a = (m1.a * m2.a + m1.b * m2.c) / 100;
    double b = (m1.a * m2.b + m1.b * m2.d) / 100;
    double c = (m1.c * m2.a + m1.d * m2.c) / 100;
    double d = (m1.c * m2.b + m1.d * m2.d) / 100;
    return new Matrix(a, b, c, d);
}

矩阵相乘：

Matrix bitZero = new Matrix(100, 0, A, B + C);
Matrix bitOne = new Matrix(A, B + C, C, A + B);
Matrix bitZeroAfterK = bitZero;
Matrix bitOneAfterK = bitOne;
for (int n = 1; n < N; n++) {
    // Maybe some Fast-Matrix-Multiplication will do it faster.
    bitZeroAfterK = multiply(bitZeroAfterK, bitZero);
    bitOneAfterK = multiply(bitOneAfterK, bitOne);
}

这样，得到系统完整的转移矩阵后，通过判断每一位bit的X和K的值，带入矩阵求出结果每一位bit的概率和期望，加权相加即可得到最后结果：

double result = 0;
for (int i = 31; i >= 0; i--) {
    result *= 2;
    Matrix matrix = isLastZero(K, i) ? bitZeroAfterK : bitOneAfterK;
    double chanceOfOne = (isLastZero(X, i) ? matrix.b : matrix.d) / 100;
    result += chanceOfOne;
}
print(t, result);

完整的代码见我的Github：company/google/NotSoRandom.java

优化方案

考虑到本题的时间复杂度与X和K的大小无关，那么主要耗时的部分是这N-1个矩阵的乘法，是不是可以使用矩阵的快速乘法（例如Strassen算法）来进一步优化时间消耗，不过我怀疑这个算法对2x2的矩阵能有多大的优化空间，我这里偷懒就没再继续研究了-。-

简介

Gson是Google发布的一个开源Java类库，能够很方便的在Java对象和JSON字符串之间进行序列化和反序列化。目前主流进行JSON解析的开源库主要有Fastjson、Jackson、Gson等，各有优劣，关于它们的对比分析见我在知乎上的这个回答：java中处理JSON的开源工具都有些什么?那个比较好用？在这篇文章中主要介绍一下Gson的进阶用法。

基本用法

Gson的基本用法非常简单，假如你有这样一个JSON文件：

{
    "name": "username",
    "age": 20,
    "admin": true
}

你只需要定义这样一个Java类：

public class User {
    private String name;
    private int age;
    private boolean admin;

    // IDE自动生成的Getter和Setter
}

然后，序列化和反序列化都只需要一句话就能搞定：

// 序列化
String string = new Gson().toJson(user);
// 反序列化
User user = new Gson().fromeJson(string, User.class);

泛型的反序列化

如果整个JSON字符串不是一个JSONObject而是JSONArray，使用上面的语句尝试反序列化时就会报错，使用类似List.class的代码无法通过编译，事实上这和Java泛型的实现机制有关系，Java的泛型对象的类型不能直接通过类型本身获取到。

在这里，Gson提供了TypeToken来实现得到泛型的实际类型，例如：

// 序列化
String string = new Gson().toJson(userList);
// 反序列化
List<User> userList = new Gson().fromeJson(string, new TypeToken<List<User>>(){}.getType());

这个TypeToken的实现过程比较精彩，对于理解Java的泛型实现有非常大的帮助，有兴趣的同学可以阅读一下TypeToken的源码。

变量名的对应

通常使用JSON的场景是从服务器端获取数据，如果服务器编写接口的人编码风格与你不一致，直接使用Gson转换而来的对象的成员变量和方法会显得非常丑陋。例如如果接口使用下划线风格命名一个变量last_login_time，那么你在调用这个变量的方法就成了user.getLast_login_time()，这是强迫症所不能忍的。

幸好Google提供了非常方便的注解功能供接口变量和Java成员变量之间的映射，你只需要这么写：

public class User {
    private String name;
    private int age;
    private boolean admin;

    @SerializedName("last_login_time")
    private String lastLoginTime;

    // IDE自动生成的Getter和Setter
}

这样Gson就能自动将JSON中的last_login_time映射为Java类中的lastLoginTime变量了，在get和set的时候也是漂亮的驼峰命名法了：user.getLastLoginTime()。

ps: 这个技巧在接口编写者英语不好的时候特别有用（逃

控制变量是否序列化

在实际使用过程中，会有各种情况导致我们的Java类与和接口JSON变量不同。比如说在本地我们需要在User类中定义一个loginTimes变量来记录登录的次数，这个变量是接口中没有的，我们序列化User传给服务器时也不希望有这个变量，如何处理这种情况呢？

Gson提供了@Expose注解来进行控制成员变量的序列化和非序列化，这个注解有两个变量：serialize和deserialize，默认都是true。需要注意的是若要使这个注解生效，必须使用GsonBuilder.excludeFieldsWithoutExposeAnnotation()方法来构建Gson对象。

如果我们在对象中使用如下注解：

public class User {
    @Expose
    private String name;
    @Expose(serialize = false)
    private int age;
    @Expose(serialize = false, deserialize = false)
    private boolean admin;

    // IDE自动生成的Getter和Setter
}

Gson gson = new GsonBuilder().excludeFieldsWithoutExposeAnnotation().create();

那么在反序列化时只会给name和age字段赋值，而序列化时只输出name字段。

与@Expose注解类似，Gson还提供了@Since注解来进行版本控制，使用GsonBuilder构建时指定版本后高于该版本的字段在序列化和反序列化时都将被忽略：

public class User {
    @Since(1.0)
    private String name;
    @Since(1.1)
    private int age;
    @Since(1.1)
    private boolean admin;

    // IDE自动生成的Getter和Setter
}

Gson gson = new GsonBuilder().setVersion(1.0).create();

此时，age和admin字段由于版本号高于Gson对象指定的1.0版本，在转换过程中会被自动忽略，也可以达到控制变量是否序列化的目的。