leetcode刷题,求hamming weight

最近看到一个不错的刷题网站leetCode,于是就去刷题啦,提高一下水平。题目真的是,很有代表性啊,我喜欢!

写一个函数,求出一个无符号整数里面位为1的个数(也就是Hamming Weight算法),例如32位整数11,用二进制表示为00000000000000000000000000001011,因此函数返回值为3

原文如下

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

对于我这种对位操作只局限于理论上的少年,可把我难住了。

开始我用的是

count += n&0x01;
n = n>>1

结果,当n为2147483648(10000000000000000000000000000000),n>>1直接变成负数,我用的语言是php和javascript,整数是有符号的,当n>>1之后,最高位的符号位变成了0,直接成了负数了!所以这个行不通了

然后看了discussion之后,发现有一个很巧妙的方法

for(; n!=0; n=n&(n-1)){
    count++;
}

这个作用是从低位依次将1置0,然后只要n不为0,就一直循环操作下去,最终的结果n肯定会为0。

当然还有hamming算法啦,这个没研究过......
想去刷题的点这里!,以后就不重复啦

你可能还喜欢下面这些文章

murmur hash,一个更快的hash算法

在打算搭建memcache集群的时候,使用了crc3算法来对key进行hash,然而发现该算法性能比较低,于是寻找一个高性能,低碰撞的hash算,很高兴有前人已经为我们发明了这种算法——murmur。MurmurHash算法:高运算性能,低碰撞率,由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年 Appleby被Google雇佣,随后Google推出其变种的CityHash算法。MurmurHash算法,自称超级快的hash算法,是FNV的4-5倍。官方数据如下:OneAtATime – 35

序言:我的sublime

多年以前有朋友推荐我用sublime,那大概是2011年的时候吧,我用tango notpad2,曾觉得这是用的最舒服的编辑器,高亮,秒开,太舒服。当我无意中看到好多人在用sublime的时候,我好奇的试一试,这一试,就是几年了,或许我以后也将会一直用下去。开始,相当长的一段时间内仅仅将sublime当做一个编辑器用,我想的是看的舒服,打开快,界面够酷就可以了,而且我用的也确实很舒服。但后来,我觉得要是sublime能够直接f5来运行程序是多方便啊,实际上,这对于sublime就是小case,sublime灵活的配置,快捷键你想怎么定义就怎么定义,只要机器上面安装了编译器或者各种语言的解释器就

Go入门:三、函数的声明和调用

这是我Go学习笔记的第三篇!接下来学习的是Go的函数声明和调用。我的语言学习过程一般分为下面几个:1. 变量和数据类型2. 流程控制方法3. 函数声明和调用4. 面向对象5. 语言特性6. 标准库函数声明func 函数名称(参数表) 返回值类型 { // 函数体}写一个函数是非常简单的,掌握语法格式就可以了。函数是一个功能的封装,能让函数体内的代码得到很好的复用。比如我要输出个人信息,我可以把个人信息封装到函数里面,后续直接调用这个函数而不是每次都print一堆信息了上面定义的函数没有参数,也没有返回值,非常简单的一个函数。如果我想让姓名可变,那么可以定义一个带有参数的函数接下来定义一个有

C++实现python字符串的endswith方法

可以使用的或方法配合比较运算符来模拟方法的功能。下面是一个示例函数,它检查一个字符串是否以另一个字符串结束:在这个示例中,函数接受两个参数:和。函数首先检查的长度是否大于或等于的长度。如果不是,那么显然不能以结束,函数返回。否则,函数使用方法从的末尾提取与长度相同的子字符串,并将其与进行比较。如果它们相等,那么以结束,函数返回。否则,函数返回。请注意,这个函数是区分大小写的。如果你想要一个不区分大小写的版本,你可以在比较之前使用和函数将和转换为小写。在这个版本中,函数首先使用和函数将和转换为小写。然后,它调用函数来检查转换后的字符串是否以结束。

c语言的位操作

一、基本位操作|或&与~取反^异或<<左移>>右移二、位操作的常见用法1.获取某位的值#define BitGet(Number,pos) ((Number)|= 1<<(pos)) //把某位置1#define BitGet(Number,pos) ((Number) &= ~(1<<(pos)) //把某位置0#define BitGet(Number,pos) ((Number) >> (pos)&1)) //用宏得到某数的某位#define BitGet(Number,pos) ((Number) ^=

C++入门:三、函数

这是我学习C++的第三篇笔记,函数。我的学习路径是现在学习的是函数的声明、定义、调用等相关知识。函数声明和定义函数的声明包含返回类型,函数名字,0个或者多个形参,无函数体,通常在头文件中对函数进行声明。函数的定义包含返回类型,函数名字,0个或多个形参,以及函数体。比如写一个求阶乘的函数,可以写成下面这样写一些简单的函数大多数语言都差不多,不过可惜每种语言或多或少都有自己的特色,这是比较令人头秃的地方。函数的参数函数可以带有0或多个参数,每个参数都需要声明类型。参数传递可以传值和传引用。如果形参是引用类型,那么它将绑定到对应的实参中,我们成为传引用。否则,将会把实参的值拷贝后赋值给形参,我们成为

位操作存取RGB颜色值的方法

分享一个位操作存取RGB颜色值的方法。缘由我需要在数据库里面存储rgb颜色,但是直接存字符串这样太low了,于是想办法 将rgb颜色经过位运算得到24位的int值,储存在mysql里面可以直接用medium int类型,很节省空间。(当然,c语言并没有24位类型,只有32位的无符号整数,在前面补8位0就ok啦,在我php中就不存在这个现象啦,哈哈)RGB三种颜色混合成一个整型操作R:255 24位二进制表示,0000 0000 0000 0000 1111 1111G:255 24位二进制表示, 0000 0000 0000 0000 1111 1111B:255 24位二进制表示, 0000

计算机语言学习指南

这篇文章讨论基于语言的基本要素,如何快速入门一种计算机语言。是一篇语言从学习到使用的指导手册,并且这种学习方式是一个系统的学习,相比于碎片化的学习,这种学习更加不容易遗忘。语言的基本成分语言的基本成分为数据、运算、控制、传输。想想你学过的语言,是不是都是这样。归结语言的组成成分,学习一门语言可以从这四个方面下手,这四个方面掌握之后,对这个语言就有个最基本的了解了。语言基本成分:数据数据是程序操作的对象。实际上我们可以思考,一个数据拥有的属性有哪些,根据我们已经掌握的语言来说(比如PHP)。$a = 1$a是数据,那么这个数据有哪些属性呢?名称(a),类型(int)。从这一行代码只能发现这两个属

python学习笔记:三、函数

这是第三篇python学习笔记,我们即将要学习python的函数。内容主要包括两个部分,函数的声明和函数的调用。函数声明和调用比如我们要声明一个“吃”的函数,语法如下:def eat(): return "eat something"print(eat())上面是一个没有参数的函数,做的事情很简单,声明一个函数,然后返回一个字符串。接下来要增加一个参数了。def ead(food): return "eat %s" % foodprint(eat('fruit'))可以看到,上面声明了一个带有一个参数的函数,当然可以声明带两个,三个等。这些都是固定的,那么如果要声明一个不固定参数的

shell中 $? $# $* $$ $* $@ $0 特殊变量含义

shell中有一些常用的难记的特殊变量,如下:$0当前脚本的文件名$n传递给脚本或函数的参数。n 是一个数字,表示第几个参数。例如,第一个参数是$1,第二个参数是$2。$#传递给脚本或函数的参数个数。$*传递给脚本或函数的所有参数。$@传递给脚本或函数的所有参数。被双引号(" ")包含时,与 $* 稍有不同$?上个命令的退出状态,或函数的返回值。$$当前Shell进程ID。对于 Shell 脚本,就是这些脚本所在的进程ID。$0 - 当前脚本文件名$n - 第n个参数$# - 参数个数$* - 所有参数$@ - 所有参数$? - 上一个命令的返回值$$ - 当前进程id

赞赏

微信赞赏支付宝赞赏

《leetcode刷题,求hamming weight》有1条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注