方法一：通过零填充右移位
 
const mid = left + right >>> 1;
 
方法二：通过Math.floor
 
const mid = Math.floor((left + right) / 2);

#问题
 
设海明码的校验位数为，数据位数为，它们需满足一个位数公式
 
 
最初看到公式时我感到很疑惑啊，百思不得其解，主要的问题是最后那个1哪来的。
 
看着公式望了半天，一点头绪都没有，好脑袋不如烂笔头，于是我开始手写举例试着理解海明码的校验逻辑。
 
不写不知道，一写吓一跳。写着写着就发现了，原来这个1来的如此妖娆。
 
#引入(海明码原理介绍)
 
我们先来复习一下二进制的划分，假设现在有七位二进制数据，用序号来指向。为什么选择七位呢？因为它们的序号刚好可以用三位二进制来表示。
 
 

我们再来看看海明码的纠错方法。
 
表示序号的三个二进制位，每一个二进制位取值为1的序号个数都是4个(图中列标红)。这冥冥之中的平衡一定可以好好利用。
 
 
我们分别把二进制3-1列取值为1的序号纳入集合A、B、C。
 
则集合取值
 
 
 
A={7,6,5,4}
 
 
B={7,6,3,2}
 
 
C={7,5,3,1}
 
 
有一种大家很熟悉，校验一个序列值的方法叫做奇偶校验，偶校验计算方式是序列中所有值异或为0。
 
如果我们按照A、B、C的集合来分类，每个集合都进行偶校验，就可以得到3个偶校验值，它们需要等于0。由于是固定的，所以A、B、C需要作为校验位参与运算。也就是需满足
 
 
 
 
 
 
 
 
 
根据异或运算的性质，自己与自己本身异或为0。所以可以得到A、B、C的计算公式
 
 
 
 
 
 
 
 
 
海明码考虑的情况是一位纠错。当某一位出错后，A、B、C和它们对应集合数据位的异或就不再是本身与本身的异或，并且最终结果会变为1。
 
也就是说，接收到数据后，若，则表示A对应集合有一位元素数据位出错了(集合对应的元素就是一列中二进制表示为1的元素)。同理，最后运算结果为0的集合对应的元素是没有问题的，这样就可以筛查出是具体哪一位元素出错，从而进行纠错。
 
比如出错，那么A=1代表第一列元素出错，B=0代表第二列元素没错，C=1代表第三列元素出错。满足所有交集的元素只有一个，也就是被筛查出来的。可以看见这种方法非常直接，因为将ABC排列成二进制数，所代表的序号就是出错的那一位。
 
如下图，红色方块代表本列有出错元素，A列确定了，C列确定了，交集；而绿色方块代表一定没有出错的元素，B列排除了。随后就被筛选出来了。
 
 
#探明
 
在上面讲述海明码纠错过程中，可能有同学已经发现问题所在了。
 
我们新增了三位校验位，可是只对七位数进行了纠错。
 
所以公式里的那个1，其实来自于我们没有画出的序号0！
 
 
我们回望A、B、C的分类，每一集合都有4个元素，看似非常规律，似乎冥冥之中决定了我们可以使用海明码这样的纠错方式。
 
偏偏卦不可算尽，虽然每集合都有4个元素，但元素的分布律不是均等的，不仅不是均等的，还遗漏了一个0。
 
所以个校验位，虽然能表示个序号，但最终只能带来的纠错能力。
 
同时我们需要将校验位加入传输数据，也就是真正的有效数据需满足
 

#ps 会什么会少一个呢？其实很简单，只要理清楚概念。k个校验位，输出的序列(比如ABC)，含义是第ABC(二进制)个序号的数值有错，而不是总共有多少个数字之类。所以看看000代表的含义就知道少掉的一种情况去哪了——它代表序列校验正确。
 
#pps 海明码校验位的位置在这个问题上没有啥作用，最初我觉得它一定有什么深层含义，想了半天也没想出什么
 
#ppps 或许以后有时间还可以写篇博客，叫做《海明码的哲学原理》。
 
 
 
 

 
hive求解中位数的几种方法
 
前言
两种解法
解法1:利用中位数的位次特征
解法2:利用升序与降序的差值
解法2.1:
  
  
延伸问题：频次+分数
参考文章

 
前言
 
假设我们有一张学生成绩表student_score，里面有三个字段：学生id：student_id,班级id：class_id,成绩：score，主键为student_id。现在让你求出每个班级学生成绩的中位数。
 
虽然hive里有内置的percentile()和percentile_approx()函数直接求解分位数，但在面试中，面试官老爷大概率不会让你直接就这么写，而是在你自信满满刷刷刷写完之后告诉你“哦，我们不能用内置函数”。
 
两种解法
 
谈到中位数，自然而然容易想到要先排序，然后根据个数的奇偶，如果是奇数个就取中间一位，如果是偶数就取中间两位的平均。关于排序，我们可以使用窗口函数row_number()，关于奇偶，我们不妨看看奇偶个数有没有共性。
 
如果总共有n个数，当n=5时，n/2=2.5，我们想要的输出是第3位；当n=6时，n/2=3，我们想要的输出是第3位和第4位的平均，那么可以发现：无论奇偶，中位数必然是在n/2和n/2+1之间的数(包含两端)的平均。
 
由此可以产生第一种解法
 
解法1:利用中位数的位次特征
 
先取出每个班级成绩排序以及总数，形成表t，再限制中位数是在n/2和n/2+1之间的数(包含两端)的平均。
 
select 
  class_id
  ,avg(score) as score_median
from
   (
    select 
          class_id
          ,score
          ,row_number() over (partition by class_id order by score asc) as score_rank
          ,count(student_id) over(partition by class_id) as student_num
    from student_score
    )t
where 
  score_rank between student_num/2 and student_num/2+1
group by 
  class_id
 
解法2:利用升序与降序的差值
 
观察如下升序编号和降序编号可以发现，当n为奇数时，中位数对应的升序编号和降序编号的差值为0，当n为偶数时，中位数对应的升序编号和降序编号的差值为1或-1
 
奇数情况
 
 
偶数情况
 

 那么通过限定升序编号和降序编号的差值为1，-1或者0，我们可以有如下写法：
 
select 
  class_id
  ,avg(score) as score_median
from
   (
    select 
          class_id
          ,score
          ,row_number() over (partition by class_id order by score asc) as score_rank_asc
          ,row_number() over (partition by class_id order by score desc) as score_rank_desc
    from student_score
    )t
where 
  (score_rank_asc- score_rank_desc) in (1,-1,0)
group by 
  class_id
 
但是解法2有一个问题，我们知道row_number处理相同值的时候会随机给一个rank，所以对于不同student_id的相同分数，可能会产生不同的rank，具体来说：
 
 这时候奇数情况也会存在升序编号和降序编号的差值为1或者-1，就会造成错误的输出。此时可以通过限定主键的方式来使得row_number对于相同分数的不同学生，降序排和升序排的名次在逻辑上是相同的(即保证五个人升序排我是第三名，降序排我也是第三名)。
 
解法2.1:
 
select 
  class_id
  ,avg(score) as score_median
from
   (
    select 
          class_id
          ,score
          ,row_number() over (partition by class_id order by score asc student_id asc) as score_rank_asc
          ,row_number() over (partition by class_id order by score desc student_id desc) as score_rank_desc
    from student_score
    )t
where 
  (score_rank_asc- score_rank_desc) in (1,-1,0)
group by 
  class_id
 
延伸问题：频次+分数
 
假设现在我们没有每个人的成绩了，只有每个班级的成绩及频次，即问题转换为：学生成绩表student_score，里面有三个字段：班级id：class_id,成绩：score，频次：frequency。现在让你求出每个班级学生成绩的中位数。
 
这时候仍然可以考虑升序和降序的频数累积和，两个数都需要大于等于总数一半，即为中位数。
 
由此有如下写法：
 
select
    class_id 
    ,avg(score) as score_median
from
(
    select 
        class_id
        ,score
        ,sum(frequency) over(partition by class_id order by score asc) as total_asc
        ,sum(frequency) over(partition by class_id order by score desc) as total_desc
        ,sum(frequency) over(partition by class_id ) as total_num
    from 
      student_score
)t
where 
  total_asc>=total_num/2
and 
  total_desc>=total_num/2
group by 
  class_id 
 
参考文章
 
 
 
 
SQL窗口函数 ↩︎
 
中位数特征 ↩︎
 
正序倒序差值 ↩︎
 
延伸问题 ↩︎
 
 

 
本文的目的是教会大家如何求出一组数据的中位数，可能一些新手朋友们还不知道什么是中位数吧？在这里就简要为大家介绍下：中位数就是一组数据按照从小到大顺序排列最中间的那个。例如：7、8、9的中位数就是8。在公式中使用到了if函数及median函数，if函数的作用就是判断，在本例中主要是判断产品是不是番茄而median函数的作用就是对数组进行中位数的计算。在文章末尾有对这两个函数的介绍大家不妨参考下。
 
解题思路
 
if函数判断B2：B7区域内的产品是不是番茄，从而返回一个数据区域{35，false，false，48,59，false}然后median函数会对该数组进行中位数的计算，结果为48.
 
案例教学
 
①通过实际的案例能更好的说明情况，我简单初略的制作了下面的表格数据，各个地区的产品数量，我们要计算出番茄的中位数。
 

 
②单击C10单元格，输入公式： =median(if(B2：B7="番茄"，C2：C7) ，大家要确保是在英文半角状态下输入的，否则会有误。
 

 
③此时按下键盘上的Ctrl+Shift+Enter三建，得到结果48，如图所示，番茄的数量是35、48、59，所以中位数是48，准确无误。
 

 
公式意义
 
if(条件，条件成立时返回什么，否则返回什么)：根据条件的成立与否返回指定的结果。
 
median(数据区域)：求出指定区域中数据的中位数。
 
上一遍：用Excel表格自制单词表实现直接默写单词不依赖背单词软件
 
下一遍：Excel中制作下拉菜单不止有数据有效性序列还有其他三种方法