Java 使用位运算 OR 对给定数组进行分割后进行 K 次循环移位来找到数组和

数组是一组具有相似的非基本数据类型（值或变量）的集合，它将元素存储在具有固定值的内存中。在创建带有特定元素的数组后，此数据集的长度变为固定。这里的非基本意味着这些数据类型可以用来调用方法来执行特定的操作，其中字符可以为空。这里的位和表示与确定地设置了 2 位的某些数字的和。位或表示每个整数都存在于子数组中。它是数组中存在的一个相邻的非空元素序列。在数组的排序操作中，有一个“半部”的概念。在这个方法中，如果可以对数组进行划分，则整个概念返回一个真值。

在本文中，我们将学习如何在进行 K 次循环移位后，在将特定的数组分割成两半的情况下，使用位或运算找到数组的和。

对整数进行 K 次循环移位的二进制表示

数据结构中的循环移位是什么

数据结构中元素的位旋转称为循环移位，它不保存特定数字的符号位。对于循环移位，有两种类型的移位方法

常规左移 − 这是一个乘法过程，由 2（模 2^N）完成。这里，N 是一个整数类型的特定位数
循环左移 − 这是一种对位数进行乘法的方法。其中乘法可以通过方法 2（模（2^N – 1））完成。

现在，假设列表中有两个正整数。通过执行循环方法，我们必须通过二进制表示交换这两个元素的位置。

左循环移位
- 最后一位将移动到第一位。
- 将所有其他位移到下一个位置。
右循环移位：
- 将第一位移动到最后。
- 将剩余位移动到前一位。

数据结构中的 K 次循环移位是什么

假设有一个长度为 N 的数组 A[]。这里 N 是一个偶数。如果 Q 是一个查询，K 是一个正数的表示。如果我们对这个数组应用循环移位，这些特定元素的和将通过对数组的半部分进行位或运算来执行。

Input: A[] = {12, 23, 4, 21, 22, 76}, Q = 1, K = 2 
Output: 117

一个循环移位的算法

步骤1 – 为该数组构建一个段树。
步骤2 – 通过 i = K%(N/2) 分配一个输入变量。
步骤3 – 然后，使用该构建的树来获取位或操作的值。
步骤4 – 第一个元素将是 (N/2) – i – 1 个元素。
步骤5 – 通过使用 [(N/2) – i 和 N – i – 1] 计算位或操作的范围。
步骤6 – 将两个结果相加以获得第 i 个数字查询的答案。

执行循环链表的循环移位的语法

struct Node {
    int data;
    struct Node * next;
};

/* Node Initialization */
struct node *last;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
struct node *four = NULL;
struct node *five = NULL;
struct node *six = NULL;

/* Allocate the memory using malloc function */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
four = malloc(sizeof(struct node));
five = malloc(sizeof(struct node));
six = malloc(sizeof(struct node));

/* Assign some data values in the list */
one->data = 1;
two->data = 2;
three->data = 3;
four->data = 4;
five->data = 5;
six->data = 6;

/* Connect the nodes with pointers */
one->next = two;
two->next = three;
three->next = four;
four->next = five;
five->next = six;
six->next = one;

/* Save address of sixth node in last position */
last = six;

在这个语法中，我们有六个节点，分别带有数据项1、2、3、4、5、6。在这里，第一个节点存储着2的地址，2存储着3的地址，依此类推。对于最后一个节点，它将指向节点一的NULL。这里的时间复杂度为O(N + Qlog(N))，辅助空间为O(4MAX)。

方法

方法1−使用Java找到数组的两个等分的按位OR。
方法2−使用Java高效地计算给定数组中所有对的按位OR之和。

使用Java找到数组的两个等分的按位OR

在这个Java构建代码中，我们将计算按位OR对的总和。这里使用I作为按位OR运算符。时间复杂度为O(n)。

示例1

import java.util.*;

public class KCTPRDD{
   static int MAX = 102001;
   static int []seg = new int[4 * MAX];
   static void build(int node, int l,int r, int a[]){
      if (l == r)
         seg[node] = a[l];

      else{
         int mid = (l + r) / 2;

         build(2 * node, l, mid, a);
         build(2 * node + 1, mid + 1, r, a);

         seg[node] = (seg[2 * node] |
            seg[2 * node + 1]);
      }
   }

   static int query(int node, int l, int r, int start, int end, int a[]) {

      if (l > end || r < start)
         return 0;

      if (start <= l && r <= end)
         return seg[node];

      int mid = (l + r) / 2;
      return ((query(2 * node, l, mid, start, end, a)) | (query(2 * node + 1, mid + 1, r, start, end, a)));
   }

   static void orsum(int a[], int n, int q, int k[]){

      build(1, 0, n - 1, a);

      for(int j = 0; j < q; j++) {
      int i = k[j] % (n / 2);
         int sec = query(1, 0, n - 1,  n / 2 - i, n - i - 1, a);
         int first = (query(1, 0, n - 1, 0,  n / 2 - 1 - i, a) | query(1, 0, n - 1,  n - i, n - 1, a));
         int temp = sec + first;
         System.out.print(temp + " ");
      }
   }
   public static void main(String[] args) {
      int a[] = { 7, 16, 10, 2001, 1997, 2022, 24, 11 };
      int n = a.length;
      int q = 2;
      int k[] = { 4, 2 };
      orsum(a, n, q, k);
   }
}

输出

4062 2078

给定数组中所有两个元素按位或的总和的高效解决方案

在这个Java代码中，我们将使用K%(N/2)的方法将每个元素移位到特定的数组中。然后遍历它以计算每个查询的两个部分的OR。

示例2

import java.io.*;

public class KCIRLLTP {
    static int pairORSum(int arr[], int n){
        int ans = 0; 
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                ans += arr[i] | arr[j];

        return ans;
    }
    public static void main(String args[]) {
        int arr[] = { 16, 07, 10, 2001, 1997 };
        int n = arr.length;
        System.out.println(pairORSum(arr, n));
    }
}