二进制中1的个数-java

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

目录

前言

一、二进制中1的个数

二、算法思路

1.将一个整数转化成二进制形式

2.查询一个数的二进制数中的第k位是多少

3.lowbit(x)操作

三、代码如下

1.代码如下:

2.读入数据

3.代码运行结果

4.样例解释

总结


前言

主要通过位运算来完成两个基本操作,查询一个数的二进制数第k位数是什么,和lowbit操作返回一个二进制数中最右边的1所对应的数值,可以用来统计二进制中1的个数。

一、二进制中1的个数

给定一个长度为 n 的数列,请你求出数列中每个数的二进制表示中 1 的个数。

输入格式

第一行包含整数 n。

第二行包含 n 个整数,表示整个数列。

输出格式

共一行,包含 n 个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围

1≤n≤100000
0≤数列中元素的值≤1000000000

二、算法思路

1.将一个整数转化成二进制形式

图1.1示例图 

将一个十进制数转换为二进制字符串,可以采用“除2取余数”的方法。具体步骤如下:

(1)将数字除以2。

(2)获取下一次迭代的整数商。

(3)获取其余的二进制数字。

(4)重复这些步骤,直到商等于0。

(5)将得到的所有余数全部排列起来,再将它反过来(逆序排列)。

上述图1.1中15的二进制数就是1111。

2.查询一个数的二进制数中的第k位是多少

图2.1示例图 

我们需要查看哪一位二进制数,只需要这个数右移多少位然后再与1做与运算即可。查看第1位就是这个数右移0位再与1做与运算;第2位是右移1位再与1做与运算后续以此类推。

         int x = 10;
         for(int i = 3;i >= 0;i--){
             pw.printf("%d",x >> i & 1);
         }
           
          
        运行结果: 1010

3.lowbit(x)操作

lowbit(x)函数的作用就是一个二进制数中最右边的1所对应的数值。

例如: x = 1010      lowbit(x) = _2{(10)} ,返回值是int对应的十进制是2;

x = 10010000  lowbit(x) = _2{(10000)},返回值是对应的十进制是16。

图3.1与运算模拟 

在计算机中我们常用补码来表示数据,其中第一位是符号位1表示正数,0表示负数。正数的原码、反码、补码全部相同;负数的反码是原码除了符号位全取反,补码是反码加1;从上述图3.1的过程中我们可以知道任意x和-x的补码对应的关系是-x的补码是x的补码连带符号位取反加1,最后二进制数中的最后一位1的后面x和-x相等,在二进制数中的最后一位1前面x和-x互相取反。

那么,进行与运算后二进制数中的最后一位1前面全部变成0,二进制数中的最后一位1后面的不变,此时就是二进制数中x的最后一位1和后面的二进制数。

 注:(与运算 1 & 0 = 0  、0 &1 = 0、1 & 1 = 1 、 0 & 0 = 0)

    //lowbit操作返回一个二进制数中最右边的1所对应的数值
    public static int lowbit(int x){
        return x & -x;
    }

三、代码如下

1.代码如下:


import java.io.*;
public class 位运算 {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws Exception{
        int n = nextInt();
        while(n-- > 0){
            int x = nextInt();
            int res = 0;
            while(x != 0){
                //每一次减去x里面的最后一位1对应的数值,减了多少次就有多少个1
                x -= lowbit(x);
                res++;
            }
            pw.print(res+" ");
        }
        pw.flush();
    }
    public static int lowbit(int x){
        return x & -x;
    }
    public static String next()throws Exception{
        return br.readLine();
    }
    public static int nextInt()throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
}

2.读入数据

5
1 2 3 4 5

3.代码运行结果

1 1 2 1 2 

4.样例解释

1对应的二进制为1,1的个数是1。

 2对应的二进制为10,1的个数为1。

3对应的二进制为11,1的个数为2。

4对应的二进制为100,1的个数为1。

5对应的二进制为101,1的个数为2。


总结

主要通过位运算来完成两个基本操作,查询一个数的二进制数第k位数是什么,和lowbit操作返回一个二进制数中最右边的1所对应的数值,可以用来统计二进制中1的个数。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/692479.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Docker的资源限制

文章目录 一、什么是资源限制1、Docker的资源限制2、内核支持Linux功能3、OOM异常4、调整/设置进程OOM评分和优先级4.1、/proc/PID/oom_score_adj4.2、/proc/PID/oom_adj4.3、/proc/PID/oom_score 二、容器的内存限制1、实现原理2、命令格式及指令参数2.1、命令格式2.2、指令参…

docker部署redis实践

1.拉取redis镜像 # 拉取镜像 sudo docker pull redis2.创建映射持久化目录 # 创建目录 sudo mkdir -p $PWD/redis/{conf,data}3. 运行redis 容器,查看当前redis 版本号 # 运行 sudo docker run --name redis -d -p 6379:6379 redis # 查看版本号 sudo docker ex…

coap:安装libcoap

# 称最新版的openssl 安装依赖东东 yum install -y libtool doxygen asciidoc perl-IPC-Cmd下载解压 cd /chz/install/openssl wget https://www.openssl.org/source/openssl-3.3.1.tar.gz tar zxvf openssl-3.3.1.tar.gz编译安装 cd /chz/install/openssl/openssl-3.3.1 .…

数据挖掘--聚类分析:基本概念和方法

数据挖掘--引论 数据挖掘--认识数据 数据挖掘--数据预处理 数据挖掘--数据仓库与联机分析处理 数据挖掘--挖掘频繁模式、关联和相关性:基本概念和方法 数据挖掘--分类 数据挖掘--聚类分析:基本概念和方法 聚类分析 聚类分析是把一个数据对象&…

计算机组成原理复习笔记

前言 就是按照考试的题型写的总结 非常应试版 题型 一、进制转换 只考 十进制 二进制 十六进制 之间的相互转换 一个个看 (1)十进制 转其他 转二进制:除以2 从小到大取余数(0或1) 转十六进制 : 除以1…

进军rust:从0开始学习rust语法

一.变量类型 Rust语言中的基础数据类型有以下几种: 1.整数型 整数型简称整型,按照比特位的长度和有无符号位可以分为以下几种 isize和usize两种整数类型是用来衡量数据大小的,它们的位长度取决于所运行的目标平台,如果是32位架…

如何在 iPhone 上恢复已删除的短信

本文介绍如何检索已删除的短信和 iMessage 以及恢复丢失的消息。说明适用于 iOS 17 及更高版本。 如何在 iOS 17及更高版本中恢复文本 恢复已删除短信的最简单方法是使用 iOS 17。从删除短信到恢复它有 30 到 40 天的时间。 在“信息”的对话屏幕中,选择“过滤器”…

老旧机子装linux——Xubuntu

目录 前言 正文 下载系统 ​编辑 制作系统盘: 安装界面 Xubuntu ​编辑 lubuntu 后语 前言 有两台电脑,一台装了Ubuntu22,一台装了debuntu。虽然debuntu界面与乌班图大体一样,但是编译器好像有点区别。由于机子为10年前的老…

二分【1】二分查找框架 查找指定元素

目录 二分查找 基本思想 几种情况汇总 一。严格递增序列 1.查找本身 2.查找第一个大于等于自己的 3.查找第一个大于自己的 4.严格递减序列 二。有重复元素 1.取其中第一个出现的 2.取其中最后一个出现的 二分查找 基本思想 几种情况汇总 一。严格递增序列 1.查找本身…

【UML用户指南】-11-对高级结构建模-高级关系

目录 1、依赖(dependency) 1.1.1、绑定(bind) 1.1.2、导出(derive) 1.1.3、允许(permit) 1.1.4、实例(instanceOf) 1.1.5、实例化(instanti…

解锁俄罗斯市场:如何选择优质的俄罗斯云服务器

在当前云计算市场上,很多大型的云厂商并没有俄罗斯服务器的云节点,这给许多企业在拓展海外业务时带来了一定的困扰。然而,俄罗斯作为一个经济发展迅速的国家,其市场潜力不可忽视。因此,选择一台优质的俄罗斯云服务器成…

Docker搭建可道云

Docker搭建可道云(存储) 文章目录 Docker搭建可道云(存储)介绍资源列表基础环境一、安装Docker二、配置Docker加速器三、搭建可道云私有云盘3.1、编写Dockerfile3.2、上传资源到指定目录3.3、查看目录下所有资源 四、构建镜像五、…

Java | Leetcode Java题解之第140题单词拆分II

题目&#xff1a; 题解&#xff1a; class Solution {public List<String> wordBreak(String s, List<String> wordDict) {Map<Integer, List<List<String>>> map new HashMap<Integer, List<List<String>>>();List<List…

HC05蓝牙模块与笔记本蓝牙连接

文章目录 1. 电脑和蓝牙模块连接 2. 串口软件调试 1. 电脑和蓝牙模块连接 HC05支持SPP协议&#xff0c;使用PC主机自带蓝牙&#xff0c;或者笔记本加蓝牙适配器。与HC05连接后&#xff0c;可在电脑端虚拟出串口&#xff0c;这样上位机软件就可以像操作串口一样与HC05通信。对…

Kafka监控系统efak的安装

下载地址Kafka Eaglehttp://download.kafka-eagle.org/下载地址连接不稳定&#xff0c;可以多次尝试直到成功连接下载 1.解压安装包并重命名 tar -zxvf kafka-eagle-bin-3.0.1.tar.gz 查看到解压后包含一个安装包&#xff0c;再解压 tar -zxvf efak-web-3.0.1-bin.tar.gz 移…

Spring Boot集成pmd插件快速入门Demo

1.什么是pmd插件&#xff1f; PMD 插件允许您在项目的源代码上自动运行PMD代码分析工具&#xff0c;并生成带有其结果的站点报告。它还支持与 PMD 一起分发的单独的复制/粘贴检测器工具&#xff08;或 CPD&#xff09;。 此版本的 Maven PMD 插件使用 PMD 6.42.0 并且需要 Jav…

在Java中使用SeleniumAPI,超详细

Java中 Selenium相关操作 1 定位元素 1.1 css选择器定位元素 就是定位到页面的元素&#xff0c;本质上就是一个一个的语法 下面举几个具体的例子&#xff1a; 类选择器 按照给定的 class 属性的值&#xff0c;选择所有匹配的元素。 语法&#xff1a;.classname 例子&am…

项目验收总体计划书(实际项目验收原件参考Word)

测试目标&#xff1a;确保项目的需求分析说明书中的所有功能需求都已实现&#xff0c;且能正常运行&#xff1b;确保项目的业务流程符合用户和产品设计要求&#xff1b;确保项目的界面美观、风格一致、易学习、易操作、易理解。 软件全套文档过去进主页。 一、 前言 &#xff0…

C++ | Leetcode C++题解之第140题单词拆分II

题目&#xff1a; 题解&#xff1a; class Solution { private:unordered_map<int, vector<string>> ans;unordered_set<string> wordSet;public:vector<string> wordBreak(string s, vector<string>& wordDict) {wordSet unordered_set(w…

一款免费文件夹同步工具,旨在帮助用户在不同磁盘或文件夹间进行文件和目录的复制、移动和同步工作

一、简介 1、一款免费文件夹同步工具&#xff0c;旨在帮助用户在不同磁盘或文件夹间进行文件和目录的复制、移动和同步工作。这款工具因其简单易用、高度可定制化的特点&#xff0c;受到了广大用户的青睐。SyncToy支持多种同步模式&#xff0c;包括镜像同步、单向同步以及增量同…