首页 > 编程语言 >基础算法篇——位运算

基础算法篇——位运算

时间:2022-11-09 07:55:07浏览次数:37  
标签:运算 int lowbit 基础 二进制 算法 公式

基础算法篇——位运算

本次我们介绍基础算法中的位运算,我们会从下面几个角度来介绍:

  • 位运算常用公式
  • 二进制中1的个数

位运算常用公式

其实位运算的使用很常见但大多不难,经常都是套用公式

我们下面分别介绍两个公式:

  1. 求第n位数
// 求n的二进制的第k位数(将n向右移动k位,相当于将求解的位数放到个位,并且将其与1进行and运算)
n >> k & 1
  1. lowbit公式
// lowbit公式用来求该二进制的最后一位1的位置
lowbit(n) = n & -n;

// 其原理很简单,n是二进制数,-n是n取反,相当于-n和n的每一位都不相同
// 但是我们再加上1,就会导致n的最后一位1的位置变成了1.相当于所有位置的值都相反,但是只有最后一位1的位置都是1

二进制中1的个数

我们来简述一下题目:

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

我们直接给出解答代码:

package cn.itcast.jvm.t1.gen;

import java.util.Scanner;

public class Sum1 {
    public static void main(String[] args) {

        // 读取n个数

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        while ( n-- > 0){

            // 读入数
            int x;
            x = scanner.nextInt();

            // 获得n后我们直接采用取n的最后一位1,并且将他减去并统计减去1的次数即可
            int res = 0;

            while (x > 0){
                x -= lowbit(x);
                res++;
            }

            System.out.println(res);
        }

    }

    // lowbit操作
    public static int lowbit(int x){
        return x & -x;
    }
}

结束语

好的,关于基础算法篇的位运算就介绍到这里,希望能为你带来帮助~

标签:运算,int,lowbit,基础,二进制,算法,公式
From: https://www.cnblogs.com/qiuluoyuweiliang/p/16871950.html

相关文章

  • JavaScript基础
    一、JavaScript基础(一)变量和数据类型1、JavaScript介绍​ 1)JavaScript是什么?​ JavaScript是运行在客户端(浏览器)的编程语言,实现人机交互。​ 2)作用​ 网页特效(监听......
  • 并行训练算法一锅炖: DDP, TP, PP, ZeRO
    本文主要参考ColossalAI论文Colossal-AI:AUnifiedDeepLearningSystemForLarge-ScaleParallelTrainingColossalAI框架开源提供了本文介绍的所有并行训练:https......
  • for和while的一些很基础的知识点 1.0版
    今天的​啊意也是忙碌的大学牲,匆匆忙忙只学了for和while很基础的一些知识点,下面便让我总结下我今天学到的东西吧下图是for执行的顺序首先就是for循环,for的基础结构就是:for......
  • 表单——前端基础
    知识点:1.表单的三元素:表单域            表单控件(表单元素)            提示信息2.在写表单元素之前,要写表单域。整个都要......
  • java——运算符
                                                        ......
  • C语言的自增自减运算符
    简单去理解,C语言的自增自减运算符的最终结果就是对自身进行加一和减一操作。但是当++、--作为后缀时则具有延后性,可能对程序有一些副作用,并且其的优先级也会对程序产生一......
  • C语言逻辑运算符
    在C语言中,逻辑运算符有&&、||、!&&表示“与”的意思,需要两端的表达式的值都为true,该式的值才为true。||表示“或”的意思,两端的表达式的值只要有一端为true,该式的值就为t......
  • C语言逗号运算符
    在C语言中,逗号运算符虽然不起眼,但也是运算符的一种,而且在所有运算符中,逗号运算符的优先级是最低的。逗号用来连接两个表达式,并以其右边的表达式的值作为它的结果。逗号的......
  • Java基础---面向对象编程
    什么是面向对象?1.面向过程思想答:线性过程第一步做什么第二步做什么2.面向对象思想答:物以类聚有,分类的思维模式,思考问题首先解决问题需要哪些分类,然后对这些分类进行......
  • 问题 J: 零基础学C/C++155——句子比较大小
    //本题考查的是二维数组的应用和strcmp和strcpy仅需对输入的字符串进行排序便可。点击查看代码#include<stdio.h>#include<string.h>#include<math.h>intmain(){......