【剑指Offer】二进制中1的个数 解题报告(Python)
2024-10-19 16:41:57
题目地址:https://www.nowcoder.com/ta/coding-interviews
题目描述
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
解题方法
这个题如果使用Python的话是有点坑的,下面说的都是Python的bin()函数处理负数时的特性。
Python的bin(n)可以得到一个数的二进制,但并不是补码表示。由于正数的补码都是本身,就不讨论了。下面看Python的bin(n)函数:
>>> bin(-7)
'-0b111'
可以看出bin(n)函数得到的是:带负号的7的二进制。但是实际上,在计算机中-7
是用补码表示的,即11111111111111111111111111111001
。
为了得到实际上的32位二进制补码,可以在python中使用n & 0xffffffff
。我们知道这一步没有对数字进行了变化,但这一步的意义是,让python把-7
的二进制补码当做正整数来看待。
>>> -7 & 0xffffffff
4294967289
再对这个正整数用bin函数就可以得到了正确的二进制补码。
>>> bin(-7 & 0xffffffff)
'0b11111111111111111111111111111001'
之后就可以用bin(n).count(‘1’)这个做法。
Python代码如下:
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
cnt = 0
if n < 0:
n = n & 0xffffffff
return bin(n).count('1')
可以使用一个mask来表示正在看到的位数,循环32次,那么就得到了每一个位置上是1的个数。
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
mask = 1
cnt = 0
for i in range(32):
if n & mask:
cnt += 1
mask <<= 1
return cnt
本题最快的解法是使用n & (n - 1)消去n最后一位的1.消了几次就是n中有几个1.
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
cnt = 0
if n < 0:
n = n & 0xffffffff
while n:
n = n & (n - 1)
cnt += 1
return cnt
Date
2018 年 3 月 10 日
最新文章
- webView 自适应高度 document.body 属性
- ParagraphString - 段落样式的简易处理
- PHP基础示例:用PHP+Mysql编写简易新闻管理系统[转]
- Inode详解-重要
- OAF 使用 javascript 使某个按钮在5秒内不能重复点击
- 滚动光效shader
- The Struts dispatcher cannot be found. This is usually caused by using Strut
- laravel5.2 移植到新服务器上除了“/”路由 ,其它路由对应的页面显示报404错误(Object not found!)———新装的LAMP没有加载Rewrite模块
- [Angular 2] Generate Angular 2 Components Programmatically with entryComponents &; ViewContainerRef
- KeilC51使用详解 (三)
- html5的本地存储localStorage和sessionStorage
- Eclipse UML 工具 ObjectAid 介绍
- Android的init过程详解(一)
- jQuery之select的option怎样绑定事件
- Java数据结构和算法 - 简单排序
- 更新mysql驱动5.1-47 Generated keys not requested. You need to specify Statement.RETURN_GENERATED_KEY
- andrroid 测试那点事
- Problem 9: Special Pythagorean triplet
- c# c/s 框架的分页用户控件,还有事件
- API的控制器
热门文章
- makefile高级用法
- C#集合Dictionary中按值的排序
- 构建LNMP+WordPress
- A Child&#39;s History of England.24
- 【leetcode】598. Range Addition II
- LinkBinTree
- When should we write our own assignment operator in C++?
- When should we write our own copy constructor?
- malloc() vs new
- 基于docker 操作mysql5.7